Sorting: More Than `sort()`

sorted() is O(n log n) and correct for nearly everything. The interesting question is what happens when O(n log n) is too slow — or when "sort" doesn't mean what you think it means.

The comparison sorts

• Timsort (Python, Java) — mergesort + insertion sort hybrid; exploits existing runs of sorted data. Best general-purpose sort.
• Quicksort — in-place on average; O(n²) worst case (bad pivot), which is why real implementations (introsort) fall back to heapsort.
• Mergesort — stable, O(n log n) guaranteed, O(n) extra memory. Good for linked lists, bad for cache locality.

Non-comparison sorts

• Counting sort — O(n + k) for small integer ranges (k = range). Counts frequencies, doesn't compare — beats comparison sorts when k is small.
• Radix sort — sorts integers digit-by-digit using counting sort — O(nk) where k is digits. Beats comparison sorts on fixed-size ints.
• Bucket sort — distribute into buckets, sort each, concatenate — good for uniform distributions.

Sorting isn't always the answer

• Top-K — a heap (O(n log k)) beats sorting the whole list (O(n log n)).
• Order statistics — quickselect finds the k-th smallest in O(n) average without full sorting.
• Is it already sorted? — a check (sorted(x) == x) costs O(n) and catches the common "I don't need to sort this" case.

Field notes

• Stability matters: a stable sort preserves the order of equal elements — sort(by=name) then sort(by=age) keeps names in order within each age group.
• The real cost of sorting isn't the sort — it's the memory access pattern; a linked-list sort is slower than an array sort even at the same complexity.