Sorting analysis
The elementary sorts all share an O(n²) worst case, but they behave very differently on real inputs. This lesson compares them side by side, live on whatever input you type.
Learning goals
- Compare best, average and worst case across elementary sorts
- Separate comparison cost from data-movement cost
- Predict behaviour on sorted, reverse and duplicate-heavy input
Prerequisites
Best/average/worst
Summary of the algorithms in this chapter. “Adaptive” means faster on nearly sorted input.
| Algorithm | Best | Average | Worst | Space | Stable | Adaptive |
|---|---|---|---|---|---|---|
| Bubble (early exit) | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Binary insertion | O(n log n) | O(n²) | O(n²) | O(1) | Yes | Partly |
| Cocktail shaker | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Comb | O(n log n) | O(n²) bound | O(n²) | O(1) | No | Partly |
| Gnome | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell (n/2 gaps) | O(n log n) | depends on gaps | O(n²) | O(1) | No | Yes |
| Cycle | O(n²) | O(n²) | O(n²) | O(1) | No | No |
Comparisons vs swaps
Comparisons and data moves cost different amounts. Comparing two ints is cheap, but comparing long strings or calling a complex Comparator is not. Moving a large struct is expensive, but moving a reference is cheap.
Selection sort makes the most comparisons and the fewest swaps. Insertion sort's shifts equal the inversion count. Cycle sort makes at most n writes. Type your own array below and compare the live counts.
Compare every elementary sort on your input
Live countsBubble sort
Selection sort
Insertion sort
Binary insertion sort
Cocktail shaker sort
Comb sort
Gnome sort
Shell sort
Cycle sort
Try “Already sorted” and “Reverse sorted” to see adaptive sorts collapse to linear work while selection sort does not change.
Sorted input
Already sorted input has zero inversions. Bubble sort with early exit, insertion, cocktail and gnome sort finish in one linear pass with no moves. Selection sort still performs all n(n-1)/2 comparisons.
In practice this matters a lot: data often arrives nearly sorted, for example timestamps or a list after one append.
Reverse input
Reverse sorted input has the maximum n(n-1)/2 inversions, which is the worst case for bubble and insertion sort: every pair must be fixed. Selection sort makes only ⌊n/2⌋ swaps here, because each swap fixes two positions.
Duplicate keys
Duplicates raise two questions: do equal keys keep their order (stability), and does the algorithm waste work moving equal keys around? Using strict > instead of >= in bubble and insertion sort keeps them stable and avoids useless moves.
When there are only a few distinct keys, counting sort (Chapter 18) or three-way partitioning in quicksort is far faster than any elementary sort.
Stability: what happens to equal keys?
InteractiveInput · letters show original order of equal keys
Insertion sort
Bubble sort
Selection sort
Shell sort
Practice ladder
Now try it yourself
Easy
- Predict comparisons and swaps of each sort on [1, 2, 3, 4, 5]
- Which sort minimises swaps on reverse input?
Medium
- Count inversions in O(n²) and check against insertion sort's shifts
- Choose a sort for 20 nearly sorted records with expensive comparisons
Advanced
- Count inversions in O(n log n) using merge sort
- Design an experiment that measures the cost of comparisons vs moves in Java
Key takeaways
- All elementary sorts are O(n²) worst case, but adaptivity and stability differ.
- Count comparisons and moves separately; which one dominates depends on the data type.
- Insertion sort is the practical winner for small or nearly sorted data.