Quick sort

Pick a pivot, move everything smaller to its left, then sort the two sides the same way.

Time O(n log n) averageSpace O(log n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Partitioning puts the pivot in its final sorted position with smaller values on the left and larger on the right. Neither side needs to look at the other again.

Code

C++PythonC#

void quickSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            swap(a[i], a[j]);
            i++;
        }
    }
    swap(a[i], a[hi]);
    quickSort(a, lo, i - 1);
    quickSort(a, i + 1, hi);
}

def quick_sort(a: list[int], lo: int, hi: int) -> None:
    if lo >= hi: return
    pivot, i = a[hi], lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    quick_sort(a, lo, i - 1)
    quick_sort(a, i + 1, hi)

public static void QuickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            (a[i], a[j]) = (a[j], a[i]);
            i++;
        }
    }
    (a[i], a[hi]) = (a[hi], a[i]);
    QuickSort(a, lo, i - 1);
    QuickSort(a, i + 1, hi);
}

Tips

Worst case is O(n²) when the pivot is always the smallest or largest, for example sorted input with a last-element pivot. A random pivot avoids it.
i marks the boundary: everything left of i is smaller than the pivot.

In the .NET library

Array.Sort starts as quick sort and falls back to heap sort if recursion gets too deep, which removes the O(n²) worst case.