Sorting Algorithms

TL;DR: Comparison sorts (merge, quick, heap) all hit the same O(n log n) wall because any comparison-only sort needs at least log(n!) comparisons. The tradeoffs separate them: quicksort is fastest in practice but has an O(n^2) worst case, merge sort is stable and predictable but uses O(n) extra space, heap sort is in-place with a guaranteed bound but cache-unfriendly. When keys are small bounded integers you beat the wall with counting or radix sort at O(n). Often the right answer is not to fully sort: use a heap for top-k or a hash for membership.

The comparison sorts and their tradeoffs

All three classic comparison sorts average O(n log n), but they fail and shine differently.

Merge sort splits in half, sorts each side, and merges. Always O(n log n), stable (equal keys keep their input order), but needs O(n) scratch space. Pick it when stability or worst-case guarantees matter; it also underlies external sorts that do not fit in memory.

Quicksort partitions around a pivot and recurses. Average O(n log n) with small constants and good cache locality, which makes it the fastest in practice. The trap is the O(n^2) worst case when pivots are bad (already-sorted input with a naive pivot). Randomized or median-of-three pivots make that case vanishingly unlikely. It is in-place but not stable.

Heap sort builds a heap then extracts the max repeatedly. Guaranteed O(n log n) and in-place (O(1) extra), but the constant factor is worse than quicksort because of poor cache behavior. Its real value is the worst-case guarantee without quicksort's risk.

Real languages blend these. Python's sorted uses Timsort (stable merge sort that exploits existing runs). C++ std::sort uses introsort, quicksort that falls back to heap sort when recursion goes too deep, keeping quicksort's speed while capping the worst case.

The O(n log n) lower bound

Any sort that only compares elements builds a decision tree: each comparison branches, each leaf is one of n! orderings. A tree with n! leaves has height at least log2(n!), which by Stirling is Θ(n log n). No comparison sort beats that; it is information-theoretic. To go faster you must stop comparing and use the structure of the keys.

Linear-time sorts when keys are bounded

If keys are integers in a known small range, sort in O(n) by counting, not comparing.

Counting sort tallies how many times each key appears, then writes them out in order: O(n + k) for n values in [0, k), useful only when k is comparable to n. Sorting a thousand values whose keys span a billion would allocate a billion-slot array.

Radix sort applies a stable counting sort to one digit at a time, least-significant first: O(d * (n + b)) for n values of d digits in base b. Both rely on the keys having exploitable structure and lose to a comparison sort once the range explodes.

def counting_sort(arr, k):           # arr values in [0, k)
    counts = [0] * k
    for x in arr:
        counts[x] += 1
    out = []
    for value, c in enumerate(counts):
        out.extend([value] * c)      # stable: equal keys stay grouped
    return out

When to sort vs use a heap or hash

Sorting is O(n log n) and gives a total order. Often you need less.

• Top-k of n (k small): a size-k heap is O(n log k), better than sorting all n. For the single max, one linear scan beats sorting.
• Membership or dedup: a hash set is O(n) and answers "is x present" without ordering anything.
• Streaming or incremental: if elements arrive over time and you always want the current min/max, a heap maintains it; re-sorting on every insert is wasteful.

The decision: do you need the full order, or just the extremes, or just membership? Only the first justifies a sort.

Why interviewers probe this

The interviewer wants to know you understand the algorithm behind sort(), not just that you can call it. The strong move when asked "how does your language sort" is to name the actual algorithm (Timsort, introsort) and its stability guarantee, then the worst-case story. That shows you read past the API.

The held-back follow-up is usually "the input is mostly sorted already, does that change anything" (Timsort exploits existing runs toward O(n)) or "you only need the 10 largest of a billion, still sorting?" (no, a size-10 heap). Both check whether you reach for sorting reflexively or pick the structure that fits the access pattern.

Common misconceptions

• "Quicksort is O(n log n), period." Its worst case is O(n^2); randomized pivots make it unlikely, not impossible. Introsort caps it.
• "Radix and counting sort beat the bound for free." Only for small bounded integer keys. The lower bound applies to comparison sorts; these are not comparison sorts.
• "All sorts are stable." Quicksort and heap sort are not. Sorting by one field then another expecting the first to break ties needs a stable sort like merge or Timsort.
• "Always sort to find the top k." A heap is O(n log k) and a single max is one O(n) pass. Sorting does work you do not need.

Key takeaways

• Comparison sorts are bounded at O(n log n) by an information-theoretic argument (log of n! orderings).
• Merge is stable and predictable but O(n) space; quicksort is fastest but O(n^2) worst case; heap sort guarantees the bound in place.
• Counting and radix sort hit O(n) only when keys are small bounded integers.
• Need just the extremes or membership, not a total order: use a heap or hash instead of sorting.