Start with the honest part#
In real code, and in an interview, you call the sort your language gives you. It is written by people who spent years on it, it is n log n, and rewriting it is a mistake.
So why learn the algorithms? Because their ideas are the answer to problems that are not about sorting. Merge sort's merge step counts inversions. Quicksort's partition step sorts three colours in one pass and finds the kth largest without sorting. If you have only ever called sort(), those look like magic.
The slow three, briefly#
Bubble, selection and insertion sort are all n². Two of them are worth one sentence each and no more.
Insertion sort is the one that earns its keep. It walks the list and drops each value back into the sorted part behind it. On a list that is nearly sorted it is close to n, because each value barely moves. That is why real library sorts switch to it for small or nearly-ordered stretches. Your language's sort is probably a hybrid with insertion sort inside it.
Selection sort's only virtue is that it makes the fewest writes, which mattered when writes were expensive. Bubble sort has no virtue and is taught first for reasons nobody can defend.
Merge sort#
Split in half, sort each half, merge the two sorted halves.
The merge is the interesting part: two sorted lists become one by repeatedly taking the smaller front. That is the two-pointer walk you already know.
| Time | n log n, always, including the worst case |
| Space | n, because the merge needs somewhere to put the result |
| Stable | Yes: equal values keep their original order |
Stability matters more than it sounds. Sort people by name, then by age, and a stable sort leaves the names in order within each age. An unstable one scrambles them, and the second sort silently undoes the first.
Merge sort is the one to reach for on a linked list, where the splitting is free and there is no random access for anything else.
Quicksort#
Pick a pivot, move everything smaller before it and everything larger after it, then sort each side.
| Time | n log n usually, n² on a bad pivot |
| Space | log n for the recursion, nothing else |
| Stable | No |
Faster than merge sort in practice, because it moves things within one array and is kind to the cache. The n² case is real: pick the first element as pivot on already-sorted input and every split is one item against the rest. Real implementations pick a random or median pivot to make that vanishingly unlikely.
The partition step is the part worth knowing. It appears on its own in sort colours, and in quickselect, which finds the kth smallest in n on average without sorting anything.
Which to name when asked#
- Stability needed or linked list: merge sort.
- Memory tight and average speed wanted: quicksort.
- Nearly sorted already: insertion sort, and say why.
- Small fixed range of values: none of them. Counting sort is
n, and sort colours is that idea with three values.
The thing under all of it#
Any sort that works by comparing pairs cannot beat n log n. There are n! possible orderings and each comparison splits the possibilities in two, so you need about log(n!) comparisons, which is about n log n. That is a proof, not a limit of cleverness.
Counting sort beats it only by refusing to compare: it uses the values as array indices, which needs them to be small integers. Whenever you see a linear-time sort, look for that trade.
Practice in order#
- Sort colours, which is the partition step with three values and no sorting algorithm at all.
- Count inversions, the problem that forces you to actually implement a merge rather than call one.
- Merge intervals and non-overlapping intervals, where sorting first is what makes the rest easy, which is the commonest use of sorting there is.
- Merge k sorted lists, which is the merge step with more than two inputs.