Quick Sort

Partition around a pivot

Pick a pivot. Rearrange so everything smaller is left of it and everything larger is right — now the pivot is in its final spot. Recurse on the two sides. Average O(n log n); worst O(n^2) if the pivot is always the min/max.

Lomuto partition

i tracks the boundary of the "smaller than pivot" zone.

def quick_sort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return a
    pivot = a[hi]
    i = 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]   # pivot to its place
    quick_sort(a, lo, i - 1)
    quick_sort(a, i + 1, hi)
    return a

Why it's the default

In place (O(log n) stack), cache-friendly, and small constants make it faster than merge sort in practice. Randomising or median-of-three pivot selection makes the O(n^2) case vanishingly rare. Not stable.

Related trick

Quickselect reuses partition to find the k-th smallest element in O(n) average without fully sorting.