Hoare's partition scheme ‐ intuition

29 Jun, 2025

Basic implementation:

    template<typename T>
    int partition(vector<T>& xs, int start, int end) {
        T pivot = xs[start];  // (a)
        int left = start - 1;
        int right = end + 1;
        while(true) {
            do {++left;} while(xs[left] < pivot);  // (b)
            do {--right;} while(xs[right] > pivot);  // (c)
            if(left >= right) return right;  // (d)
            swap(xs[left], xs[right]);  // (e)
        }
    }

Notes:

1. In (a) it is important to select left as pivot, so in (b) and © we don't need boundary checks - pivot naturally guards boundaries.
   • after the first while iteration, (e) ensures that pivot is to the right of left and some x < pivot is to the left of right.
2. (d) returns right, and not left, because left was incrementing and stopped where xs[left] >= pivot.
   • If xs[left] == pivot, then right decrementing stopped at xs[right] == pivot and right == left, so everything before right is <= pivot.
   • If xs[left] > pivot, then right decrementing stopped at xs[right] < pivot and right == left - 1, so everything before right is <= pivot again.
   • In any case every element in xs[start..right] inclusive is <= pivot and every element in xs[right+1..end] inclusive is >= pivot, but pivot duplicates can be on both sides.

#algorithms