Sorting
See how seven sorting strategies create order through different invariants.
The idea
Comparison sorts build order through local swaps, insertion, recursive merging, pivot partitioning, or a heap. Their frames emphasize the invariant that grows after every operation.
Counting and bucket sort trade comparisons for a sensible numeric range: values become counts or enter ordered range buckets before reconstruction.
Sorting a hand of cards can mean swapping neighbors, inserting each new card, dividing piles and merging them, or grouping cards into labeled trays.
When to reach for it
- You need ascending order before searching or scanning.
- The input is small enough to compare strategies visually.
- A bounded integer range makes counting or bucket distribution efficient.
Language-independent template
choose a sorting invariant
repeat its compare, move, divide, or distribute step
until every position is finalComplexity — time O(n log n) typical; O(n²) elementary, space O(1) to O(n + range) (The selected mode determines the exact bounds.).
Common mistakes
- Losing equal or duplicate values during a swap or merge.
- Recursing on the pivot again in quicksort.
- Using range-based sorts when maximum minus minimum is too large.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Sort every value in ascending order without library sorting.
Sort three value classes in-place.
Count smaller values to the right of every position.