Sorting Algorithms Side by Side
The six algorithms start with the same array and perform the same number of basic operations (one comparison or one write) at each step. So "speed" here is not clock time but operation count, which is exactly what we count in algorithm analysis. Red bars are the elements being compared, green bars the ones just written. Each algorithm shows its finishing position. The pseudocode and complexity of the algorithm you select are shown below.
What to notice
- On a random array raise $n$ from 30 to 120: the operation count of the $O(n^2)$ algorithms grows about 16-fold, that of the $O(n \log n)$ ones about 5 to 6-fold.
- On "nearly sorted" input Insertion Sort and Bubble Sort beat everyone: their best case is $O(n)$. What you know about the input changes which algorithm to choose.
- On "reversed" input Quick Sort collapses: with the pivot always at the extreme it falls into its worst case, $O(n^2)$. Merge Sort and Heap Sort are unaffected.
- Selection Sort makes the same number of comparisons whatever the input, but it also makes the fewest writes: at most $n - 1$ swaps.
- The AP Computer Science A curriculum includes Selection Sort, Insertion Sort and Merge Sort.