algorithms · high

Quick Sort

Quick sort chooses a pivot and partitions the array so smaller elements go left and larger go right, fixing the pivot in its final position, then recurses on each side. It averages O(n log n), is in-place, and has excellent cache behavior, which makes it the usual default — but a bad pivot on already-sorted data degrades to O(n^2). Production sorts use median-of-three pivot selection and switch to heap sort at deep recursion (introsort).

The code

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1; // pivot = last element
    for (int j = lo; j < hi; ++j)
        if (a[j] < pivot)
            std::swap(a[++i], a[j]);
    std::swap(a[i + 1], a[hi]); // pivot to its final position
    return i + 1;
}
void quickSort(int a[], int lo, int hi) {
    if (lo >= hi)
        return;
    int p = partition(a, lo, hi); // pivot now in place
    quickSort(a, lo, p - 1);      // recurse left
    quickSort(a, p + 1, hi);      // recurse right
}

What this lesson walks through

1. 01Quick sort — partition around a pivot
2. 02Pivot 4 lands in place
3. 03Pivot 2 lands in place
4. 04Pivot 5 lands in place
5. 05Pivot 9 lands in place
6. 06Pivot 7 lands in place
7. 07Sorted

Quick sort picks a pivot (here the last element), partitions the array so everything smaller is left of it and everything larger is right, which puts the pivot in its FINAL position. Then it recurses on each side.