Card 01/ 08
Choosing a Sort by Memory, Stability and Worst Case
Five questions about the keys, the spare memory and the worst input that pick a sort, or send you to the built-in one.
Choosing a sorting algorithm means reading the program's constraints before its data: how much memory is spare, whether equal keys must keep their order, how bad the worst input may be, and what the keys look like. This card covers the properties that separate the sorts, and a sequence of questions that turns them into a choice.
A payroll system sorts 40,000 employees by department every night. A watch sorts the last 60 heart-rate readings with a few hundred bytes free. A trading system must sort each batch of orders before a deadline that a slow input would miss. Each of them would pick a different sort, and none of them would pick it by asking which sort is fastest.
Four properties do the separating. A sort's worst-case time is its running time on the input that makes it slowest. Its extra space is the memory it needs besides the items themselves. It is stable when items with equal keys come out in the order they went in, which matters whenever an item carries more than its key. It is adaptive when it runs faster on input that is already nearly sorted. The table sets the sorts from the earlier topics against these four, where n is the number of items, k the number of possible key values for counting sort, and d and b the digits and base for radix sort.
| Sort | Worst time | Extra space | Stable | Adaptive |
|---|---|---|---|---|
| Insertion sort | O(n²) | O(1) | Yes | Yes, O(n) on sorted input |
| Selection sort | O(n²) | O(1) | No | No |
| Merge sort | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(1) | No | No |
| Quicksort | O(n²), O(n log n) on average | O(log n) stack, recursing into the smaller side first | No | No |
| Counting sort | O(n + k) | O(n + k) | Yes | No |
| Radix sort | O(d · (n + b)) | O(n + b) | Yes | No |
No row wins every column. The two O(n log n) comparison sorts trade with each other: merge sort is stable and needs n more cells, heapsort needs no memory and is not stable. Quicksort is usually the fastest on average and alone has a quadratic worst case among them. Sorts exist that are stable, in place and O(n log n) at once, the block merge sorts, but they are intricate and lie beyond this subject.
The questions below turn the table into a choice. Ask them in order and stop at the first that fits; the early ones rule out the most.
When The keys are integers in a small range, or fixed-width keys such as 32-bit integers or short codes, and there is room for an array of counts
, chooseA linear-time sort: counting sort for a small range, radix sort for fixed-width keys
When There are only a few dozen items, or the items are already nearly sorted
, chooseWhen Equal keys must keep their input order, and there is room for n more items
, chooseWhen There is no room beyond a few variables, and every input must finish in O(n log n)
, chooseWhen Average speed matters most, a rare O(n²) input is acceptable, and the stack can grow to about log n
, choose
Otherwise Nothing here constrains the program: call the language's built-in sort, as Built-In Sorts in Python, Java and TypeScript shows.
A choice made the other way round shows why the order matters. A team that picks quicksort because it is fastest on average, for a log whose entries must keep their order within each second, has picked a sort that is not stable and will shuffle those entries; the third question would have sent them to merge sort.
Use the questions when the program has a constraint the built-in sort does not meet: no spare memory, a deadline every input must meet, keys a linear-time sort can read, or a language whose built-in sort is not stable for the items in hand. Most programs have none of these, and the built-in sort, tuned for years, is the right call.
The constraints decide the sort; speed on a typical input decides it only when nothing else does.
← → move through sections and cards