Quick SortQuicksort

01Why it exists

Reach for it when you see:In-place sorting, stability not required, fastest on average, pivot, partition, k-th smallest / median / percentile, three-way partitioning for heavy duplicates, the language's built-in sort.

02The core idea

Quicksort is divide and conquer run backwards. Merge sort splits straight down the middle and does its work in the merge; quicksort does all of its work up front, in the partition: pick a pivot, move everything ≤ pivot to the left and everything > pivot to the right. Once that is done, nothing on the pivot's left is larger than it and everything on its right is larger, so the pivot is already standing in its final sorted position and never needs to move again. Recurse into the two halves and you are finished — there is no merge step, and every swap happens inside the original array.

Why is it correct? The Lomuto partition used in the demo takes a[hi] as the pivot and uses i and j to cut the range into three parts, maintaining the invariant that a[lo..i] are all ≤ pivot, a[i+1..j-1] are all > pivot, and a[j..hi-1] has not been examined. When it looks at a[j]: if it is > pivot, advancing j folds it into the second part automatically; if it is ≤ pivot, i advances one slot first and then a[i] and a[j] are swapped, which moves the large element at the head of the second part to its tail and folds a[j] into the first part. Either way all three properties survive. When the sweep ends the third part is empty, and swapping the pivot into i+1 gives you "left ≤ pivot < right". Then induct on length: once both halves are sorted recursively, every value on the left is ≤ pivot < every value on the right, so the whole range is sorted.

Complexity: all the partitions at one level of the recursion scan O(n) elements between them, so the running time comes down to how many levels there are. When the pivot splits down the middle every time, T(n) = 2T(n/2) + O(n), log n levels, O(n log n); when it is an extreme value every time (already-sorted data with the pivot fixed at the end), T(n) = T(n−1) + O(n), n levels, O(n²). Switch to a random pivot and, with distinct elements, the expected number of comparisons is about 2n ln n ≈ 1.39 n log₂ n no matter how the input was arranged, so no permutation reliably triggers the worst case. As for space, partitioning is in place and the only extra cost is the recursion stack: O(log n) deep on average, but O(n) in the worst case if you recurse into both sides. Recursing into the shorter side only and continuing on the longer one with a loop at least halves the range at every level down, which caps the depth at log₂ n — that is where the O(log n) space comes from.

There are three pitfalls worth knowing. The first is heavy duplicates: Lomuto sends every element equal to the pivot to the left, so when all the values are identical each pass removes exactly one element and a random pivot cannot save you. Use a three-way partition instead, splitting into < pivot, == pivot and > pivot, which places the whole middle block at once. The second is that quicksort is not stable: long-distance swaps scramble the order of equal elements — partitioning [2₁, 2₂, 1] around 1 gives [1, 2₂, 2₁]. The third is forgetting to exclude the pivot from the recursive ranges: written as [lo, p], the range may not shrink at all and the recursion never ends. Against the neighbouring lessons: merge sort is O(n log n) even in the worst case and stable, but needs an O(n) scratch array; heapsort is O(n log n) in the worst case with only O(1) space, but its jumpy memory access makes it slower in practice. So unstable built-in sorts are mostly quicksort with a safety net (introsort switches to heapsort when the recursion gets too deep and to insertion sort on small ranges), while anything that has to be stable — Python's sorted, Java's object sort — uses the merge-based Timsort.

03The algorithm

1. 1If the range [lo, hi] holds 0 or 1 elements (lo >= hi), return immediately.
2. 2Pick a random index in [lo, hi] and swap it with a[hi] to make it the pivot.
3. 3Lomuto partition: i = lo − 1; sweep j from lo to hi − 1, and whenever a[j] <= pivot, do i += 1 and swap a[i] with a[j].
4. 4After the sweep, swap a[i+1] with a[hi]. The pivot's final position is p = i + 1.
5. 5Handle [lo, p−1] and [p+1, hi]: recurse into the shorter side, and for the longer one update lo or hi and loop back to step 1. That keeps the stack depth under log n.
6. 6With heavy duplicates in the data, switch to a three-way partition (the three pointers lt, i, gt) and never recurse into the block equal to the pivot. If you only need the k-th smallest, use Quick Select and follow only the part k falls in.

04Interactive demo

The shared array is [5, 2, 9, 1, 7, 3, 8, 4], and the pivot is always the last element of the range — a Lomuto partition with no randomisation, so every playthrough is identical. Yellow is the pivot, blue marks the two cells just swapped, green marks elements already in their final place, and grey is outside the current range; while a partition runs, the rows underneath list the ≤ pivot region, the > pivot region and the elements not yet examined. The first cut uses 4 as the pivot and splits 3 against 4, which is reasonably even. The next three partitions use 3, 5 and 7, each of which happens to be the extreme value of its range, so the range shrinks by only one each time — this is what degrading to O(n²) looks like.

05Code

The Lomuto partition (the one from the demo), quicksort with a random pivot that only recurses into the shorter side, the three-way variant for heavy duplicates, and Quick Select built on that three-way partition. Both partitions are shown because Lomuto is the easiest to follow, but only the three-way version survives heavy duplicates — which is also why Quick Select uses it.

import random


def partition(a, lo, hi):
    """Lomuto partition: a[hi] is the pivot. Returns where the pivot ends up."""
    pivot = a[hi]
    i = lo - 1                              # everything in a[lo..i] is <= pivot
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]       # pivot moves between the two parts and never moves again
    return i + 1


def quick_sort(a, lo=0, hi=None):
    """Random pivot + recurse into the shorter side: O(n log n) average, O(log n) stack depth"""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        r = random.randint(lo, hi)          # pick a random pivot, swap it to the end, then partition
        a[r], a[hi] = a[hi], a[r]
        p = partition(a, lo, hi)
        if p - lo < hi - p:                 # left side is shorter: recurse left, let the loop take the right
            quick_sort(a, lo, p - 1)
            lo = p + 1
        else:
            quick_sort(a, p + 1, hi)
            hi = p - 1
    return a


def partition3(a, lo, hi):
    """Three-way partition: a[lo..lt-1] < pivot, a[lt..gt] == pivot, a[gt+1..hi] > pivot"""
    pivot = a[random.randint(lo, hi)]
    lt, i, gt = lo, lo, hi
    while i <= gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1                         # the swapped-in element is unseen, so i stays put
        else:
            i += 1
    return lt, gt


def quick_sort_3way(a, lo=0, hi=None):
    """No degradation on heavy duplicates: the whole == pivot block is placed at once"""
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return a
    lt, gt = partition3(a, lo, hi)
    quick_sort_3way(a, lo, lt - 1)
    quick_sort_3way(a, gt + 1, hi)
    return a


def quick_select(a, k):
    """The k-th smallest value (k is 0-based), O(n) average; reorders a"""
    lo, hi = 0, len(a) - 1
    while True:
        lt, gt = partition3(a, lo, hi)
        if k < lt:
            hi = lt - 1                     # the answer is on the left, throw the whole right away
        elif k > gt:
            lo = gt + 1
        else:
            return a[k]                     # k lands inside the "== pivot" block


if __name__ == "__main__":
    b = [5, 2, 9, 1, 7, 3, 8, 4]
    print(partition(b, 0, len(b) - 1), b)   # 3 [2, 1, 3, 4, 7, 9, 8, 5] (the demo's first partition)
    print(quick_sort([5, 2, 9, 1, 7, 3, 8, 4]))           # [1, 2, 3, 4, 5, 7, 8, 9]
    print(quick_sort_3way([3, 1, 3, 3, 2, 1, 3, 2]))      # [1, 1, 2, 2, 3, 3, 3, 3]
    nums = [5, 2, 9, 1, 7, 3, 8, 4]
    print(quick_select(nums[:], 3))                       # 4 (4th smallest)
    print(quick_select(nums[:], len(nums) - 2))           # 8 (2nd largest)

06Practice

• LeetCode 905Sort Array By Parity (one partition: evens left, odds right)Easy
• LeetCode 75Sort Colors (three-way partition, also known as the Dutch national flag problem)Medium
• LeetCode 2161Partition Array According to Given Pivot (relative order must be preserved, which swap-based partitioning destroys)Medium
• LeetCode 912Sort an Array (always taking the last element as pivot times out; add randomisation and three-way partitioning)Medium
• LeetCode 215Kth Largest Element in an Array (Quick Select; watch out for heavy duplicates)Medium
• LeetCode 324Wiggle Sort II (Quick Select for the median, then a three-way partition)Medium