Sorting II: Merge Sort & Quicksort

Merge sort: always O(n log n)

Merge sort applies divide and conquer verbatim: split the array in half, sort each half recursively, then merge the two sorted halves. There are about log2(n) levels of splitting, and each level does O(n) work merging, giving O(n log n) in every case — best, average, and worst.

The heart is the merge step: given two sorted runs, repeatedly take the smaller front element. It needs an extra array of size n — merge sort uses O(n) extra space — and it's stable (ties take the left run first).

// merge sorted a[lo..mid] and a[mid+1..hi] into a, using buffer tmp
void merge(int a[], int tmp[], int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= keeps it stable
    while (i <= mid) tmp[k++] = a[i++];   // leftovers, left run
    while (j <= hi)  tmp[k++] = a[j++];   // leftovers, right run
    for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}

The merge step: walk two sorted runs, always emitting the smaller front.

Quicksort: partition around a pivot

Quicksort divides differently. Pick one element as the pivot, then partition: rearrange the array so everything smaller sits left of the pivot and everything larger sits right. The pivot is now in its final position; recurse on the left and right parts. No merge needed — the combine is free.

Partition [ 3  7  1  6  2 ] with pivot = 2 (last element):

  scan, swapping elements < pivot to the front:
  [ 1  3  7  6 | 2 ]   ( 1 < 2, moved left )
  place pivot after the small ones:
  [ 1 | 2 | 3  7  6 ]
        ^pivot now in final spot; recurse on [1] and [3 7 6]

Partition splits around the pivot; the pivot lands in its final position.

// Lomuto partition: pivot = a[hi]; returns pivot's final index
int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) std::swap(a[i++], a[j]); // small ones to front
    std::swap(a[i], a[hi]);                         // pivot into place
    return i;
}
void quicksort(int a[], int lo, int hi) {
    if (lo >= hi) return;                  // base case
    int p = partition(a, lo, hi);
    quicksort(a, lo, p - 1);
    quicksort(a, p + 1, hi);
}

Quicksort sorts in place — only the recursion stack is extra space.

Pivot choice is everything

If the pivot reliably splits the array near the middle, quicksort is O(n log n) on average — and its tight inner loop makes it fast in practice. But a *bad* pivot (e.g. always the smallest) splits off just one element each time, giving n nested levels and O(n^2) worst case. Quicksort uses O(log n) stack space when balanced.

Good pivot (near middle)        Bad pivot (always smallest)

   [........n........]            [........n........]
     /           \                pivot | [....n-1....]
  [n/2]        [n/2]                       pivot | [..n-2..]
  / \           / \                              pivot | [n-3]
 ...           ...                                    ...
 ~log n levels, O(n) each       n levels, O(n) each
   => O(n log n)                  => O(n^2)

Balanced splits give O(n log n); lopsided splits degrade to O(n^2).

Which one — and what std::sort does

Need a guaranteed O(n log n) and stability (e.g. linked lists, external/multi-key sorts)? Choose merge sort.
Sorting an in-memory array and want raw speed with little extra space? Quicksort (with a good pivot) usually wins.
In practice, just call std::sort — it's an introsort: quicksort that falls back to heapsort to dodge O(n^2), and to insertion sort on tiny subarrays.

#include <algorithm>
#include <vector>
std::vector<int> v = {5, 2, 8, 1};
std::sort(v.begin(), v.end());          // O(n log n), introsort
std::stable_sort(v.begin(), v.end());   // O(n log n), stable (merge-based)

Prefer the standard library; reach for std::stable_sort when ties must keep order.

The lesson is broader than sorting: knowing *how* an algorithm achieves its complexity — and where it can fail — lets you pick the right tool and trust the library to handle the rest. Next we ask the deeper question: is O(n log n) the fastest sorting can ever be?