F4.03 · part 3 of 3
Stability & sort cost
Sorts are ranked on more than their average speed. Three numbers matter — average case,
worst case, and extra space — plus one yes/no property: stability, whether elements with
equal keys keep their original order. And over all of them sits a hard floor: any sort that works purely by
comparing elements needs at least about n log n comparisons in the worst
case. No cleverness escapes it.
Compare the three sorts on the numbers that decide which one to reach for, then see why
n log n is a wall.
Ranking the sorts
Merge sort wins on guarantees: O(n log n) in every case and stable, at the price of O(n) extra space. Quicksort is often fastest in practice and sorts in place, but its worst case is O(n²) and it is not stable. Insertion sort is O(n²) but tiny and stable, and unbeatable on nearly-sorted input. Select one to read its card.
The algorithm · select one
There is no single best sort — there is the one whose trade-offs fit your data. Need a guarantee and stable output? Merge. Tight memory and random data? Quick. Small or nearly-sorted? Insertion.
Advanced: the n log n lower bound
Why can no comparison sort beat O(n log n)? Think of the sort as a decision tree. Each comparison
it makes is one yes/no branch, and to sort correctly it must reach a different leaf for every possible input
ordering. There are n! orderings of n elements, so the tree
needs at least that many leaves — and a binary tree with n! leaves is at least
log₂(n!) deep. By Stirling’s approximation that is about
n log n, so some input always forces that many comparisons.
The escape hatch is to stop comparing. Counting sort and radix sort use the keys themselves as indices and run in O(n), but only when the keys are bounded integers — they trade generality for speed. For arbitrary orderings, merge sort already sits on the floor.
A comparison sort is a decision tree · n! leaves, height ≈ n log n
n! distinct leaves
takes at least log₂(n!) levels. That is the O(n log n) floor —
merge sort touches it, quicksort touches it on average, and nothing comparison-based goes below it.# Elixir's Enum.sort is a stable merge sort — O(n log n), guaranteed Enum.sort([3, 1, 2]) # => [1, 2, 3] Enum.sort_by(users, & &1.age) # stable: equal ages keep input order # the floor, informally: # n elements have n! orderings # one comparison = one yes/no branch # distinguishing n! outcomes needs >= log2(n!) ~ n*log2(n) comparisons
The idea
A comparison answers one yes/no question; ordering n things needs about log₂(n!) of them.
In Elixir
Enum.sort meets the n log n floor and is stable; only key-based sorts go lower.
That completes F4.03. Next module: F4.04 — Maps, sets & hashing (in production), where hashing trades ordering away to make lookup O(1) on average — the door into the trie family that closes out the chapter.
References
Primary sources for this lesson, and where it connects in the course.
Sources
- Merge sort — Wikipedia — a stable functional sort.
- Cormen, Leiserson, Rivest & Stein (2022). Introduction to Algorithms (4th ed.). — sorting and searching, including the comparison-sort lower bound.