Quicksort and Quickselect

Quicksort picks a pivot, partitions the array so that smaller elements come before it and larger ones after it, and recurses on the two sides. There is nothing to merge afterwards. With a random pivot it runs in expected O(n log n) and sorts in place, which is why variants of it power most standard library sorts. Its sibling, quickselect, recurses into only one side and finds the k-th smallest element in expected linear time, one of the most frequently asked interview tricks.

Intuition

• Partition is the core. After partitioning around a pivot value p, every element left of the pivot block is smaller than p, every element right of it is larger, and the pivot block is already in its final sorted position.
• Recursion: sort the left part and the right part independently. Because partitioning already put everything on the correct side, concatenation is free.
• Why a random pivot: a bad pivot (the minimum or maximum) leaves one side with n - 1 elements, giving T(n) = T(n - 1) + O(n) = O(n^2). Always picking the first or last element triggers exactly that on sorted input. With a uniformly random pivot, any two elements a_i < a_j (by rank) are compared only if one of them is the first pivot chosen among the values between them, which happens with probability 2 / (j - i + 1). Summing over all pairs gives about 2n ln n comparisons: expected O(n log n).
• Three-way partition: with many equal keys, a two-way partition can still go quadratic (an array of identical values never splits). Splitting into < p, == p and > p groups (the Dutch national flag scheme) makes duplicates free: the equal block is never touched again.
• Quickselect: to find the element of rank k, partition once. If k falls inside the pivot block you are done; otherwise continue only on the side that contains k. The expected work is n + n/2 + n/4 + ... = O(n).

When to use it in interviews / OAs

• "Find the k-th largest / smallest element", "find the median", "k closest points", "top k by some score": quickselect in expected O(n), or a size-k heap in O(n log k) when the data is streaming.
• "Implement a sort without the library": randomized quicksort or merge sort.
• Problems that are really a partition: sort colors (three values), move zeros, segregate even and odd numbers, partition a list around a value.
• Follow-ups about worst cases, stability, or why the standard library uses introsort.

Template

Three-way partition

import random


def partition3(a: list, lo: int, hi: int) -> tuple[int, int]:
    """Partition a[lo..hi] (inclusive) around a random pivot.
    Afterwards a[lo:lt] < pivot, a[lt:gt + 1] == pivot, a[gt + 1:hi + 1] > 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  # do not advance i: the element swapped in is unexamined
        else:
            i += 1
    return lt, gt

Quicksort

Recursing into the smaller side and looping on the larger side keeps the recursion depth at O(log n) even when partitions are unbalanced:

def quicksort(a: list, lo: int = 0, hi: int | None = None) -> None:
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        lt, gt = partition3(a, lo, hi)
        if lt - lo < hi - gt:  # recurse on the smaller part, loop on the larger
            quicksort(a, lo, lt - 1)
            lo = gt + 1
        else:
            quicksort(a, gt + 1, hi)
            hi = lt - 1

Quickselect

def quickselect(a: list, k: int):
    """Return the k-th smallest element (0-based). Reorders a in place."""
    lo, hi = 0, len(a) - 1
    while True:
        lt, gt = partition3(a, lo, hi)
        if k < lt:
            hi = lt - 1
        elif k > gt:
            lo = gt + 1
        else:  # k lands inside the block equal to the pivot
            return a[k]


def kth_largest(nums: list[int], k: int) -> int:
    """k is 1-based: k = 1 is the maximum."""
    return quickselect(nums, len(nums) - k)

After quickselect(a, k) returns, the array is also partitioned around position k: everything before it is no larger and everything after it is no smaller. That is exactly what "k closest points" or "top k" questions need, without sorting the rest.

Complexity

• Quicksort: expected O(n log n) time; worst case O(n^2), made vanishingly unlikely by random pivots. Extra space is O(log n) for the recursion when you recurse on the smaller side first. Not stable.
• Quickselect: expected O(n), worst case O(n^2). A deterministic pivot rule (median of medians: groups of five, recursive median of their medians) guarantees O(n) in the worst case, but its constant factor is large and it is beyond typical interview scope.
• Library sorts: C++ std::sort is introsort (quicksort that falls back to heap sort when recursion gets too deep, plus insertion sort for tiny ranges), so it is O(n log n) worst case. std::nth_element is the library quickselect. Python has no quickselect; heapq.nlargest(k, nums) is O(n log k).

Common pitfalls

• Fixed pivot (first or last element). Sorted or reverse-sorted input becomes O(n^2), and so does a crafted test case. Pick a random pivot.
• Two-way partition with many duplicates. An all-equal array never splits. Use the three-way partition.
• Advancing i after swapping with gt. The element that arrives from the right has not been examined yet.
• Inclusive versus exclusive bounds. Keep hi inclusive everywhere or exclusive everywhere; mixing them causes infinite loops or skipped elements.
• k-th largest index conversion. The k-th largest (1-based) is the element of 0-based rank n - k in ascending order.
• Mutating the caller's array. Quickselect reorders its input; copy it first if the caller still needs the original order.
• Deep recursion in Python. Without the smaller-side trick, a bad run can exceed the recursion limit.

Interview variations

• Kth largest element: quickselect, or a min-heap holding the k largest seen so far.
• K closest points to the origin and top k frequent elements: quickselect over the squared distances or frequencies (partition indices by that key), then return the first k.
• Sort colors: run the same three-way loop with the pivot fixed to 1; one pass, O(1) space.
• Median of an unsorted array: quickselect for rank n // 2 (and n // 2 - 1 for even n).
• Wiggle sort: find the median with quickselect, then three-way partition around it with interleaved positions (a harder follow-up).
• Why is quicksort often faster than merge sort in practice? It works in place, with sequential memory access and a small constant factor; merge sort needs O(n) extra memory but is stable and worst-case O(n log n).