Sorting Algorithms

Comparison-based sorting is bounded below by $O(n\log n)$; know merge sort, quicksort, and heapsort tradeoffs.

1. The idea

No comparison-based sorting algorithm can beat $O (n lo g n)$ in the worst case — this follows from an information-theoretic argument: there are $n!$ possible orderings, and each comparison yields at most one bit of information, so you need at least $lo g_{2} (n!) = O (n lo g n)$ comparisons.

Merge sort guarantees $O (n lo g n)$ worst-case time by recursively splitting and merging, using $O (n)$ extra space; it's stable (preserves relative order of equal elements). Quicksort averages $O (n lo g n)$ with small constants and $O (lo g n)$ space, but degrades to $O (n^{2})$ on adversarial or already-sorted input without randomized pivoting. Heapsort guarantees $O (n lo g n)$ with $O (1)$ extra space but isn't stable and has worse cache performance in practice.

Non-comparison sorts like counting sort or radix sort can achieve $O (n + k)$ or $O (nk)$ time when the data has special structure (e.g., bounded integer range), breaking the $O (n lo g n)$ lower bound because they don't rely on pairwise comparisons.

2. Why it matters

Interviewers expect you to know which sort to use when, why $O (n lo g n)$ is a hard floor for comparison sorts, and when specialized sorts beat that floor.

3. Core mathematics

Comparison sort lower bound

Ω (n lo g n)

From $lo g_{2} (n!)$ via Stirling's approximation

Merge sort

T (n) = 2 T (n /2) + O (n) = O (n lo g n)

O(n) extra space, stable

Quicksort

O (n lo g n) average, O (n^{2}) worst case

Counting sort (integers in range k)

O (n + k)

4. How to recognize it

Think of this when…

Asks to sort data and analyze best/average/worst-case complexity
Compares stability, space usage, or worst-case guarantees between sorting algorithms
Data has bounded range (e.g., grades 0-100), hinting at non-comparison sorts

5. Worked example

Worked example

You need to sort 1 million integers known to lie between 0 and 100. What's the most efficient approach and its complexity, versus using a generic comparison sort?

1
Comparison sort (e.g. merge sort) gives O(n log n) regardless of the value range.
$O (n lo g n) \approx 1 0^{6} \times 20 = 2 \times 1 0^{7} comparisons$
2
Counting sort exploits the bounded range k=101: count occurrences of each value, then output in order.
$O (n + k) = O (1 0^{6} + 101) \approx 1 0^{6}$
Answer: Counting sort is asymptotically faster here, O(n+k) versus O(n log n), because the small bounded range avoids the comparison-based lower bound.

6. Common mistakes

Assuming quicksort's worst case is O(n log n) — it degrades to O(n^2) on adversarial input without safeguards like random pivots
Forgetting merge sort's O(n) extra space requirement when space is constrained
Applying counting/radix sort to data without a small bounded range, losing its efficiency advantage

7. Quick check

The worst-case lower bound for any comparison-based sort on n elements is:

Which sort has O(n^2) worst-case time without mitigation (e.g. random pivot)?

8. Practice

1 QuantSolve questions use this concept.

Practice this concept

9. Related methods

This lesson is conceptual; see the topic hub for methods.

Create a free account to save lesson progress.