Partitioning, quicksort and selection

Merge sort splits the input by position and does its work while merging. Quicksort splits by value — everything small to the left, everything large to the right — and then there is nothing left to merge. That one step, partitioning around a pivot, is the whole skill: get its invariant right and quicksort, quickselect (std::nth_element) and a dozen interview problems follow from it.

1. Partitioning with an invariant

Partitioning rearranges a range so that every element satisfying a predicate comes before every element that doesn't. Lomuto's scheme walks once with two indices and keeps this invariant:

#include <cstddef>
#include <print>
#include <span>
#include <utility>
#include <vector>

// Moves every element < pivot to the front; returns how many there are.
std::size_t partition_less(std::span<int> v, int pivot) {
    std::size_t store = 0;                 // [0, store) < pivot
    for (std::size_t i = 0; i < v.size(); ++i)
        if (v[i] < pivot)
            std::swap(v[store++], v[i]);   // grow the < region by one
    return store;                          // [store, n) >= pivot
}

int main() {
    std::vector<int> v{7, 2, 9, 4, 1, 8, 3};
    auto k = partition_less(v, 5);
    std::println("{} elements < 5: {}", k, v);
}

Check it against the invariant: when v[i] < pivot, swapping it with v[store] (the first >= element, or itself) extends the < region and keeps the >= region contiguous. When v[i] >= pivot, incrementing i alone extends the >= region. At the end [i, n) is empty.

The result is not sorted and not stable — the order within each side is whatever the swaps produced. That's the point: partitioning is O(n), and it's enough to put the pivot itself in its final sorted position.

Hoare's scheme, the original, scans from both ends towards the middle and swaps pairs that are on the wrong side. It does about a third as many swaps, and handles equal keys better (both scans stop on them), but its invariant and the boundary it returns are subtler. Lomuto is easier to get right; real libraries use Hoare-style loops.

2. Three-way partitioning (the Dutch national flag)

With two-way partitioning, keys equal to the pivot all end up on one side. For a range of a million equal keys every partition is maximally unbalanced. Dijkstra's three-way partition keeps four regions instead:

#include <cstddef>
#include <print>
#include <span>
#include <utility>
#include <vector>

struct Bounds {
    std::size_t lt, gt;  // [0, lt) <, [lt, gt) ==, [gt, n) >
};

Bounds partition3(std::span<int> v, int pivot) {
    std::size_t lt = 0, i = 0, gt = v.size();
    while (i < gt) {                                     // unknown region non-empty
        if (v[i] < pivot)      std::swap(v[lt++], v[i++]);
        else if (pivot < v[i]) std::swap(v[i], v[--gt]); // don't advance i!
        else                   ++i;
    }
    return {lt, gt};
}

int main() {
    std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    auto [lt, gt] = partition3(v, 3);
    std::println("lt={} gt={}: {}", lt, gt, v);
}

Note the asymmetry. Swapping with v[lt] brings in an element we've already seen (it was in the == region, or it's v[i] itself), so i advances. Swapping with v[gt - 1] brings in an element from the unknown region, so i must stay put and examine it next.

3. Quicksort

Partition around a pivot, then sort each side. After a three-way partition the == region is already in place, so it's excluded from both calls:

void quicksort(std::span<int> v) {
    if (v.size() < 2) return;
    int pivot = choose_pivot(v);
    auto [lt, gt] = partition3(v, pivot);
    quicksort(v.first(lt));        // < pivot
    quicksort(v.subspan(gt));      // > pivot — [lt, gt) is done
}

Cost. Each level of recursion partitions every element once: O(n) per level. With balanced splits there are log₂ n levels: O(n log n). If each partition only peels off one element, there are n levels: O(n²) — and n nested calls, which overflows the stack long before a million elements.

When does that happen?

With the first (or last) element as pivot, sorted input is the worst case: the pivot is the minimum, the left side is empty, the right side has n − 1 elements. Reversed input too. Real data is often sorted or nearly sorted, so this isn't a theoretical concern.

Choosing the pivot

A random pivot makes the expected cost O(n log n) for every input: no fixed order is bad. Picking the median of three random samples makes very lopsided splits unlikely, too.

Bounding the stack

Even with good pivots, recursion depth depends on luck. One trick fixes it: recurse into the smaller side, loop on the larger. The recursive call gets at most half the elements, so the depth is at most log₂ n — guaranteed.

while (v.size() > 16) {
    auto [lt, gt] = partition3(v, pivot_of(v));
    auto left = v.first(lt), right = v.subspan(gt);
    if (left.size() < right.size()) { quicksort(left);  v = right; }
    else                            { quicksort(right); v = left;  }
}
insertion_sort(v);   // small ranges: lower overhead wins

What std::sort actually is

std::sort is introsort: quicksort with median-of-three pivots, plus a depth counter; if recursion exceeds about 2 log₂ n levels it switches that range to heapsort, which guarantees O(n log n) in the worst case. Small ranges finish with insertion sort. It's not stable — use std::stable_sort (a merge sort) when equal keys must keep their order.

4. Quickselect: the k-th smallest in O(n)

To find the k-th smallest element you don't need both sides — only the one that contains position k. That turns quicksort's two recursive calls into one loop:

#include <cstddef>
#include <print>
#include <span>
#include <utility>
#include <vector>

struct Bounds { std::size_t lt, gt; };

Bounds partition3(std::span<int> v, int pivot) {
    std::size_t lt = 0, i = 0, gt = v.size();
    while (i < gt) {
        if (v[i] < pivot)      std::swap(v[lt++], v[i++]);
        else if (pivot < v[i]) std::swap(v[i], v[--gt]);
        else                   ++i;
    }
    return {lt, gt};
}

// k-th smallest, 0-based. (Middle pivot here for brevity; use a random one.)
int kth_smallest(std::span<int> v, std::size_t k) {
    std::size_t lo = 0, hi = v.size();          // position k is in [lo, hi)
    while (true) {
        auto part = v.subspan(lo, hi - lo);
        int pivot = part[part.size() / 2];
        auto b = partition3(part, pivot);
        std::size_t lt = lo + b.lt, gt = lo + b.gt;
        if (k < lt)      hi = lt;               // answer is among the smaller
        else if (k < gt) return pivot;          // k landed on the pivot's run
        else             lo = gt;               // answer is among the larger
    }
}

int main() {
    std::vector<int> v{9, 1, 8, 2, 7, 3, 6, 4, 5};
    std::println("median = {}", kth_smallest(v, v.size() / 2));
}

With balanced splits the work is n + n/2 + n/4 + … < 2n: expected O(n), better than sorting. The standard library's version is std::nth_element, which reorders the range so that v[k] is what it would be after sorting, everything before it is <=, and everything after it >=.

Faded example — your turn

top_k(v, k) should return the k largest elements in any order, in expected O(n). Use quickselect: which position do you select, and which part of the range is the answer afterwards?

std::vector<int> top_k(std::vector<int> v, std::size_t k) {
    // select position ???, then return the elements from ??? to the end
}

5. The standard library's partition algorithms

#include <algorithm>
#include <print>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};
    std::ranges::stable_partition(v, [](int x) { return x % 2 == 0; });
    std::println("{}", v);   // evens first, each group in original order

    std::vector<int> w{9, 1, 8, 2, 7, 3};
    std::ranges::nth_element(w, w.begin() + 2);
    std::println("third smallest: {}", w[2]);
}

Every one of them needs a strict weak ordering when it takes a comparator: comp(a, a) must be false. Passing <= instead of < breaks the algorithms' assumptions — std::sort can then run off the end of the range.

Summary

• Partitioning is one O(n) pass with a stated invariant; write the regions down before writing the loop.
• Three-way partitioning handles duplicates: all equal keys are done at once.
• Quicksort's cost depends on the pivot: first-element pivots make sorted input O(n²) and O(n) deep. Use a random (median-of-three) pivot.
• Recurse into the smaller side and loop on the larger to bound the stack at O(log n). std::sort is introsort: this plus a heapsort fallback.
• Quickselect keeps one side per step: expected O(n) — std::nth_element.