Level 2 · 35 min

Sorting: Comparison vs Linear Time

Sorting is not one algorithm; it is a family of trade-offs around comparisons, memory, stability, and input shape. Senior answers name the constraints before naming quicksort or mergesort.

The comparison lower bound

Any sort that only learns by comparing pairs has a lower bound of Omega(n log n) comparisons. Quicksort, mergesort, and heapsort live in this world. The choice depends on worst-case guarantees, extra memory, stability, and cache behavior.

Stability and memory matter

A stable sort preserves the relative order of equal keys. This matters when sorting records by secondary keys or building deterministic pipelines. Mergesort is naturally stable but needs extra memory. Heapsort is in-place with strong worst-case time but often slower in practice due to cache misses.

Linear-time sorting has assumptions

Counting sort, radix sort, and bucket sort beat n log n by exploiting structure: bounded integer ranges, fixed-width digits, or distribution assumptions. They are not magic; they trade comparisons for extra memory and assumptions about keys.

Key Takeaways

Comparison sorting cannot beat Omega(n log n) in the general case.
Stable, in-place, worst-case optimal, and cache-friendly cannot all be maximized at once.
Linear-time sorts are valid only when key constraints justify the memory and preprocessing.

Code example

function countingSort(values, maxValue):
  counts = array(maxValue + 1, fill = 0)
  for value in values:
    counts[value] += 1
  output = []
  for value from 0 to maxValue:
    repeat counts[value] times:
      output.append(value)
  return output