Sorting I: Merge Sort, Quicksort, and Heapsort — The O(n log n) Algorithms

In plain words — and an analogy

Imagine sorting a deck of shuffled playing cards. One strategy: split the deck in half, give each half to a friend to sort, then merge the two sorted halves by repeatedly taking the smaller top card — that is merge sort. Another strategy: pick any card as a 'pivot', put all lower cards to the left of it and all higher to the right, then recursively sort each pile — that is quicksort. A third strategy: first build a heap (a structure that always exposes the largest card on top), then repeatedly pull the top card to its final position — that is heapsort. All three reach O(n log n), but their personalities are very different.

Sorting is foundational far beyond producing ordered lists: it unlocks binary search, enables two-pointer techniques, simplifies deduplication and grouping, and is a building block inside countless other algorithms. This lesson covers the three classic O(n log n) comparison sorts — each a case study in a design paradigm — and the theory that says you can't do asymptotically better with comparisons alone.

The O(n log n) lower bound

Why can't a comparison sort beat n log n? Any such sort distinguishes outcomes only by comparing pairs of elements, and there are n! possible orderings to tell apart. Each comparison has two outcomes, so a decision tree of comparisons needs at least log₂(n!) ≈ n log n levels to reach n! distinct leaves. That's a *proof*, not a limitation of cleverness: Ω(n log n) is the floor for comparison sorting. (Beating it requires not comparing — counting and radix sorts, next lesson, exploit the values themselves.)

Sort [a, b, c]. First compare a vs b:

              a < b?
             /      \
         YES            NO
        b < c?         a < c?
       /     \        /     \
    YES       NO   YES       NO
   [a,b,c]  a<c? [b,a,c]  [b,c,a]
            / \
          YES  NO
        [a,c,b] [c,a,b]

Leaves (outcomes) = 6 = 3!
Tree depth = 3 = ⌈log₂(6)⌉

For n elements: n! leaves → depth ≥ log₂(n!) ≈ n log n
→ Every comparison sort needs Ω(n log n) comparisons worst-case.

Merge sort: stable divide-and-conquer

Merge sort is divide and conquer in its purest form: split the array in half, recursively sort each half, then *merge* the two sorted halves into one.

MergeSort(arr, lo, hi):
  if lo >= hi: return           // base case: 0 or 1 element

  mid = (lo + hi) // 2
  MergeSort(arr, lo, mid)       // sort left half
  MergeSort(arr, mid+1, hi)     // sort right half
  Merge(arr, lo, mid, hi)       // combine

Merge(arr, lo, mid, hi):
  left  = arr[lo..mid]          // copy to temp buffers
  right = arr[mid+1..hi]
  i, j, k = 0, 0, lo
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:     // <= preserves stability
      arr[k++] = left[i++]
    else:
      arr[k++] = right[j++]
  while i < len(left):  arr[k++] = left[i++]
  while j < len(right): arr[k++] = right[j++]

Worked example: merge sort recursion tree

              [5, 2, 4, 1, 3]          ← divide
             /                \
        [5, 2, 4]          [1, 3]
        /       \           /   \
     [5, 2]    [4]        [1]   [3]
     /    \
   [5]   [2]

Now combine (merge) bottom-up:
  [5],[2]   → merge → [2, 5]
  [2,5],[4] → merge → [2, 4, 5]
  [1],[3]   → merge → [1, 3]
  [2,4,5],[1,3] → merge → [1, 2, 3, 4, 5]  ✓

Each level does O(n) merge work. There are log₂(5) ≈ 3 levels.
Total: O(n log n).

The merge is the heart: two sorted lists combine in O(n) via a single linear pass. The recursion tree is log n levels deep, each doing O(n) total merge work → O(n log n) always — best, average, and worst case are identical, which is a genuine strength when you need predictability. Merge sort is also stable (equal elements keep their original relative order — crucial when sorting records by a secondary key) and it parallelizes and works beautifully on linked lists and data too big for memory (external sort). Its cost: O(n) extra space for the merge buffer, which rules it out where memory is tight.

Quicksort: fast in-place partitioning

Quicksort also divides and conquers, but does its work *before* recursing rather than after. Pick a pivot, partition the array so everything smaller sits left of the pivot and everything larger sits right (the pivot is now in its final sorted position), then recursively sort the two sides. No merge step, and the partition is done in place.

QuickSort(arr, lo, hi):
  if lo >= hi: return
  p = Partition(arr, lo, hi)
  QuickSort(arr, lo, p - 1)
  QuickSort(arr, p + 1, hi)

Partition(arr, lo, hi):          // Lomuto scheme
  pivot = arr[hi]                // pick last element as pivot
  i = lo - 1                     // i = boundary of smaller elements
  for j in range(lo, hi):
    if arr[j] <= pivot:
      i++
      swap(arr[i], arr[j])       // grow the left region
  swap(arr[i+1], arr[hi])        // place pivot in final position
  return i + 1                   // pivot index

Worked example: quicksort partition step

arr = [3, 6, 8, 10, 1, 2, 1]
       lo=0                hi=6  pivot=arr[6]=1

i = -1   (boundary starts before the array)

j=0: arr[0]=3  > pivot(1)  → no swap;  i=-1
j=1: arr[1]=6  > pivot(1)  → no swap;  i=-1
j=2: arr[2]=8  > pivot(1)  → no swap;  i=-1
j=3: arr[3]=10 > pivot(1)  → no swap;  i=-1
j=4: arr[4]=1 <= pivot(1)  → i=0, swap arr[0] and arr[4]
     arr = [1, 6, 8, 10, 3, 2, 1]
j=5: arr[5]=2  > pivot(1)  → no swap;  i=0

Place pivot: swap arr[i+1]=arr[1] with arr[hi]=arr[6]
     arr = [1, 1, 8, 10, 3, 2, 6]
Return pivot index = 1

State after partition:
  Left  [1]  |  pivot 1  |  Right [8, 10, 3, 2, 6]
  Everything left  ≤ pivot  ≤  everything right ✓

When partitions are balanced (pivot near the median), the recursion is log n deep with O(n) work per level: O(n log n) average, and with small constants plus cache-friendly in-place access, quicksort is typically the *fastest in practice*. The catch: a *bad* pivot (e.g., always the smallest element, which happens if you pick the first element on already-sorted input) partitions into sizes 0 and n−1, making the recursion n deep → O(n²) worst case. The fix is standard and important: randomize the pivot (or use median-of-three), which makes the worst case astronomically unlikely on any fixed input. Quicksort is not stable and uses O(log n) stack space for the recursion.

Heapsort: the guaranteed in-place bound

Heapsort uses the heap from Lesson 13: build a max-heap from the array in O(n), then repeatedly extract the maximum (swap the root to the end, shrink the heap, sift down) — each extraction places the next-largest element into its final slot. After n extractions the array is sorted, in place.

HeapSort(arr):
  n = len(arr)

  // Phase 1: build max-heap in O(n) using sift-down heapify
  for i in range(n // 2 - 1, -1, -1):
    SiftDown(arr, i, n)

  // Phase 2: extract max repeatedly
  for end in range(n - 1, 0, -1):
    swap(arr[0], arr[end])       // move max to its final position
    SiftDown(arr, 0, end)        // restore heap property on arr[0..end-1]

SiftDown(arr, i, size):
  while True:
    largest = i
    left, right = 2*i+1, 2*i+2
    if left  < size and arr[left]  > arr[largest]: largest = left
    if right < size and arr[right] > arr[largest]: largest = right
    if largest == i: break
    swap(arr[i], arr[largest])
    i = largest

Heapsort's distinctive selling point is a guaranteed O(n log n) worst case with O(1) extra space — it never degrades like quicksort and never needs merge sort's buffer. Its downside is worse constants and cache behavior than quicksort (heap operations hop around memory via index arithmetic rather than scanning linearly), and it's not stable. It's the safe choice when you need worst-case guarantees *and* minimal memory.

The three compared

This is why real library sorts are hybrids: introsort starts with quicksort and switches to heapsort if recursion goes too deep (capturing quicksort's speed *and* heapsort's worst-case guarantee), while timsort blends merge sort with insertion sort and exploits existing runs (giving stability and near-O(n) on partly-ordered data). The lesson: the 'best' sort depends on your constraints — stability, memory, worst-case tolerance — not on Big-O alone, since all three share it.

When to use which sort

• Need stability? Merge sort (or timsort). Quicksort and heapsort silently reorder equal elements.
• Memory constrained? Heapsort for guaranteed O(n log n) with O(1) space; quicksort for O(log n) stack space.
• Fastest in practice? Quicksort — but always randomize the pivot or use median-of-three.
• Predictable worst case? Merge sort or heapsort — quicksort's O(n²) is rare but real.
• Linked lists? Merge sort — random access for quicksort's pivot selection is expensive on linked lists.
• Nearly sorted / small subarrays? Insertion sort — its O(n) best case beats everything else; real hybrids switch to it below ~10–20 elements.

Common pitfalls

• Not randomizing quicksort's pivot. A fixed pivot (first/last element) makes sorted or reverse-sorted input hit the O(n²) worst case — a real denial-of-service risk. Randomize, or use median-of-three.
• Assuming any O(n log n) sort is stable. Only merge sort (and timsort) is stable among these. If equal-key order matters, quicksort and heapsort will silently reorder ties.
• Ignoring merge sort's memory. Its O(n) buffer can be prohibitive on huge arrays or embedded systems — that's precisely when heapsort's O(1) space wins.
• Re-implementing a sort in production. Standard-library sorts are tuned hybrids that beat naive re-implementations; write your own only to learn, or for genuinely special constraints.
• **Forgetting the O(n log n) barrier is only for *comparison* sorts.** If keys are small integers, the next lesson's non-comparison sorts break it.

Practice problems

1. Kth largest element. Find the k-th largest element in an unsorted array. (Quickselect — the partition step of quicksort — solves this in O(n) average without fully sorting the array.)
2. Sort colors (Dutch national flag). Given an array of values 0, 1, 2 (representing three colors), sort them in one pass with O(1) space. This is Dijkstra's three-way partition — a variant of quicksort's partition using two pivot boundaries.
3. Merge k sorted lists. Given k sorted linked lists, merge them into one sorted list. (Use a min-heap of size k, pulling the smallest head from each list at each step — O(n log k) where n is total elements.)

Key takeaways

• Comparison sorting can't beat O(n log n) — it's a proven lower bound via the decision-tree argument.
• Merge sort: always O(n log n), stable, O(n) space — predictable and ideal for linked lists and external data.
• Quicksort: O(n log n) average and fastest in practice, but O(n²) worst case unless you randomize the pivot; in-place, not stable.
• Heapsort: guaranteed O(n log n) with O(1) space, not stable, poorer cache behavior — the memory-safe worst-case choice.
• Real sorts are hybrids (introsort, timsort); pick based on stability, memory, and worst-case needs, since Big-O ties them.

Those were comparison sorts. But if your keys are bounded integers, you can sort in *linear* time by not comparing at all — counting, radix, and bucket sort, next. Drill sort trade-offs in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play