Why selection sort and insertion sort are essentially the same algorithm in disguise
You might think selection sort and insertion sort are distinct methods for organizing data, but they are fundamentally identical. While they appear to behave differently, they actually perform the exact same set of operations. The difference lies only in the order of execution, not the underlying logic of the process.
At the core of sorting algorithms lies the way they decompose a problem. Professor Graham Hutton explains that when you strip away implementation details, selection sort and insertion sort are two sides of the same coin. Both methods ultimately execute the same 'triangle' of operations to arrange a set of numbers. The distinction between them is merely a matter of perspective regarding the order in which these operations are carried out.
To visualize this, imagine a grid of operations. Selection sort processes this grid one column at a time, while insertion sort works through it one row at a time. Despite this difference in direction, the total work performed remains consistent. The confusion often arises because people focus on how specific programs implement these methods rather than the essential logic behind the algorithms themselves.
Implementation details, such as whether a process is sequential or parallel, or whether it uses an imperative or functional approach, can obscure this underlying similarity. For instance, a sequential implementation might allow a row to stop comparing numbers once the correct insertion point is found. However, these are optimizations dependent on the specific computational model, not inherent features of the sorting methods. By focusing on the essential decomposition of the problem, it becomes clear that these two classic algorithms are performing the same fundamental task in different sequences.
Understanding this equivalence is important for computer science because it highlights the difference between an algorithm's essential logic and its practical implementation. What seems like a different strategy is often just a different path to the same result. By looking past the surface-level mechanics, we can see the elegant, shared structure that defines these two foundational approaches to sorting.
Source: Sorting Secret - Computerphile
