Quick Sort

Sorting O(n log n) O(log n)

Divide-and-conquer sort that partitions the array around a pivot, then recursively sorts each side.

Idle

Starting Quick Sort on 8 elements.

InvariantEverything left of i is < pivot; everything between i and j is ≥ pivot. The pivot lands between them.

1/31

comparisons0swaps0lo0hi0pivot0i0j0

compareswapshiftselectsorted

quick-sort.c

int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i + 1]; arr[i + 1] = arr[hi]; arr[hi] = tmp;
    return i + 1;
}
 
void quickSort(int arr[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(arr, lo, hi);
        quickSort(arr, lo, p - 1);
        quickSort(arr, p + 1, hi);
    }
}

How Quick Sort works

Pick a pivot and partition: smaller values to its left, larger to its right — the pivot lands in its final place. Recurse on the two sides. Everything happens in place.

Best case

Balanced partitions (good pivots): O(n log n) with a very small constant.

Worst case

Sorted input with a bad pivot rule — one-sided partitions: O(n²).

When to use it

The default general-purpose in-memory sort when stability is not required.