Quicksort — Algorithms & DS

Partition: the core operation

Quicksort picks a pivot element and partitions the array so that everything less than the pivot is to its left, and everything greater is to its right. The pivot is now in its final sorted position. Recursively sort both sides.

c

static void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int partition(int *arr, int lo, int hi) {
    int pivot = arr[hi - 1];  // last element as pivot
    int i = lo;
    for (int j = lo; j < hi - 1; j++)
        if (arr[j] <= pivot) swap(&arr[i++], &arr[j]);
    swap(&arr[i], &arr[hi - 1]);
    return i;
}

void quicksort(int *arr, int lo, int hi) {
    if (hi - lo <= 1) return;
    int p = partition(arr, lo, hi);
    quicksort(arr, lo, p);
    quicksort(arr, p + 1, hi);
}
          

The pivot problem

The worst case — O(n²) — happens when the pivot is always the smallest or largest element. Every partition produces one subarray of n−1 elements and one of 0. The recursion goes n levels deep, doing O(n) work each level.

This happens on already-sorted input when picking the first or last element as pivot — a common case in practice. Solutions: pick the median of three elements as pivot, or shuffle the array before sorting (randomized quicksort).

⚠️

Quicksort is not stable. The partition step moves elements past each other regardless of equality. Use merge sort when stable ordering of equal elements is required.

Why it wins in practice

Quicksort works entirely in-place — O(log n) stack space for the recursion, no auxiliary array. Everything happens within the original array, giving excellent cache locality. Merge sort's auxiliary buffer means twice the memory traffic. For typical inputs on modern CPUs, quicksort's cache advantage outweighs merge sort's guaranteed worst-case bound.

The C standard library's qsort() uses quicksort variants. C++'s std::sort uses introsort — quicksort that falls back to heapsort if the recursion depth exceeds O(log n), preventing the O(n²) worst case.

one-line takeaway

Quicksort wins on real hardware through cache efficiency — but pivot choice is everything.