Comparison-Based Sorting: Merge Sort, Quick Sort, and Heap Sort

Terminology

• Comparison-based sorting: any sorting algorithm that determines element order solely by comparing pairs of elements using a less-than or equal-to operator.
• In-place: an algorithm that sorts using only $O(1)$ extra memory beyond the input array (or $O(\log n)$ for recursion stack).
• Stable sort: a sort that preserves the relative order of elements with equal keys.
• Divide and conquer: a strategy that breaks a problem into smaller subproblems, solves each recursively, then combines the results.
• Pivot: in Quick Sort, the element chosen to partition the array into two halves.
• Heap property: in a max-heap, every parent node is greater than or equal to its children.
• Amortized cost: the average cost per operation over a sequence of operations, even if individual operations vary.
• Recurrence relation: an equation that defines a function in terms of its value at smaller inputs, used to analyze recursive algorithm complexity.
• $\Omega(n \log n)$ lower bound: the theoretical minimum number of comparisons any comparison-based sort must make in the worst case.

What & Why

Sorting is one of the most studied problems in computer science. Given an array of n elements, produce a permutation where every element is less than or equal to the one that follows it.

Why does sorting matter so much? Because it unlocks faster algorithms everywhere else. Binary search requires sorted data. Database query optimizers sort intermediate results. Merge operations in distributed systems depend on sorted streams. Even rendering engines sort objects by depth before drawing.

Comparison-based sorts determine order by comparing pairs of elements. There is a proven lower bound: any comparison-based sort must perform at least \Omega(n \log n) comparisons in the worst case. The three algorithms in this post all achieve O(n \log n) time (at least on average), making them asymptotically optimal.

Each one makes a different trade-off:

• Merge Sort: always O(n \log n), stable, but needs O(n) extra space
• Quick Sort: O(n \log n) average with small constants, in-place, but O(n^2) worst case
• Heap Sort: O(n \log n) worst case, in-place, but not stable and has poor cache behavior

How It Works

Merge Sort

Merge Sort splits the array in half, recursively sorts each half, then merges the two sorted halves into one sorted array. The merge step walks through both halves simultaneously, always picking the smaller element.

Quick Sort

Quick Sort picks a pivot element, partitions the array so that everything less than the pivot goes left and everything greater goes right, then recursively sorts each side. The key insight: after partitioning, the pivot is already in its final sorted position.

The partition step is where the real work happens. The Lomuto scheme walks a single pointer through the array, swapping elements smaller than the pivot to the front. The Hoare scheme uses two pointers converging from both ends.

Heap Sort

Heap Sort first builds a max-heap from the array in O(n) time (using the bottom-up heapify approach). Then it repeatedly extracts the maximum element (the root), places it at the end of the array, and restores the heap property on the reduced heap. After n extractions, the array is sorted.

Complexity Analysis

Merge Sort Recurrence

Merge Sort splits the array in half and does $O(n)$ work to merge:

By the Master Theorem (case 2, $a = 2$, $b = 2$, $f(n) = n$):

Quick Sort Average Case

When the pivot splits the array into roughly equal halves on average, the recurrence is the same as Merge Sort. The worst case ($O(n^2)$) occurs when the pivot is always the smallest or largest element, producing maximally unbalanced partitions:

Randomized pivot selection makes the worst case astronomically unlikely in practice.

The \Omega(n \log n) Lower Bound

Any comparison-based sort can be modeled as a binary decision tree. With $n!$ possible permutations, the tree needs at least $n!$ leaves. A binary tree with $L$ leaves has height at least $\log_2 L$:

This means no comparison-based sort can do better than $O(n \log n)$ in the worst case.

Implementation

Merge Sort

ALGORITHM MergeSort(A, left, right)
  INPUT: array A, indices left and right
  OUTPUT: A[left..right] sorted in place

  IF left >= right THEN RETURN

  mid = left + (right - left) / 2
  MergeSort(A, left, mid)
  MergeSort(A, mid + 1, right)
  Merge(A, left, mid, right)
END

ALGORITHM Merge(A, left, mid, right)
  INPUT: array A with A[left..mid] and A[mid+1..right] each sorted
  OUTPUT: A[left..right] merged and sorted

  CREATE temp array of size (right - left + 1)
  i = left
  j = mid + 1
  k = 0

  WHILE i <= mid AND j <= right DO
    IF A[i] <= A[j] THEN
      temp[k] = A[i]
      i = i + 1
    ELSE
      temp[k] = A[j]
      j = j + 1
    END IF
    k = k + 1
  END WHILE

  WHILE i <= mid DO
    temp[k] = A[i]
    i = i + 1
    k = k + 1
  END WHILE

  WHILE j <= right DO
    temp[k] = A[j]
    j = j + 1
    k = k + 1
  END WHILE

  COPY temp[0..k-1] into A[left..right]
END

Quick Sort (Lomuto Partition)

ALGORITHM QuickSort(A, low, high)
  INPUT: array A, indices low and high
  OUTPUT: A[low..high] sorted in place

  IF low >= high THEN RETURN

  pivotIndex = Partition(A, low, high)
  QuickSort(A, low, pivotIndex - 1)
  QuickSort(A, pivotIndex + 1, high)
END

ALGORITHM Partition(A, low, high)
  INPUT: array A, indices low and high
  OUTPUT: index where pivot is placed

  pivot = A[high]
  i = low - 1

  FOR j = low TO high - 1 DO
    IF A[j] <= pivot THEN
      i = i + 1
      SWAP A[i] AND A[j]
    END IF
  END FOR

  SWAP A[i + 1] AND A[high]
  RETURN i + 1
END

Heap Sort

ALGORITHM HeapSort(A, n)
  INPUT: array A of size n
  OUTPUT: A sorted in ascending order

  // Build max-heap (bottom-up)
  FOR i = n/2 - 1 DOWNTO 0 DO
    SiftDown(A, i, n)
  END FOR

  // Extract elements one by one
  FOR end = n - 1 DOWNTO 1 DO
    SWAP A[0] AND A[end]
    SiftDown(A, 0, end)
  END FOR
END

ALGORITHM SiftDown(A, i, size)
  INPUT: array A, index i, heap size
  OUTPUT: subtree rooted at i satisfies max-heap property

  largest = i
  left = 2 * i + 1
  right = 2 * i + 2

  IF left < size AND A[left] > A[largest] THEN
    largest = left
  END IF

  IF right < size AND A[right] > A[largest] THEN
    largest = right
  END IF

  IF largest != i THEN
    SWAP A[i] AND A[largest]
    SiftDown(A, largest, size)
  END IF
END

Real-World Applications

• Standard library sorts: most language runtimes use hybrid approaches. Python's Timsort combines Merge Sort with Insertion Sort. C++'s std::sort uses Introsort (Quick Sort + Heap Sort fallback).
• Database query processing: external merge sort handles datasets larger than memory by sorting chunks on disk and merging them.
• Distributed systems: MapReduce's shuffle phase merge-sorts intermediate key-value pairs across nodes.
• Operating systems: process schedulers use heap-based priority queues, which rely on the same sift-down operation as Heap Sort.
• Version control: Git's merge operations on sorted diff hunks use the same two-pointer merge logic as Merge Sort.

Key Takeaways

• All three algorithms achieve $O(n \log n)$ time on average, matching the theoretical lower bound for comparison-based sorting
• Merge Sort guarantees $O(n \log n)$ worst case and is stable, but costs $O(n)$ extra space
• Quick Sort is the fastest in practice due to small constants and cache-friendly access, but has an $O(n^2)$ worst case that randomized pivots effectively eliminate
• Heap Sort is $O(n \log n)$ worst case and in-place, but poor cache locality makes it slower in practice than Quick Sort
• Real-world implementations are hybrids: Timsort, Introsort, and pdqsort combine these algorithms to get the best of each