Quicksort

Merge sort did its work in the merge step: splitting was cheap, merging was expensive. Quicksort reverses this — splitting is expensive, and there is no merge.

The idea is this: an element is chosen (the pivot), and the array is split in two — those smaller than it and those larger. The pivot is now in its final position; the two parts are sorted independently, and because they already sit side by side, no additional operation is needed.

Partitioning

Partitioning chooses the last element as the pivot and splits the array into two regions in a single pass.

def partition(d: list[int], start: int, end: int) -> int:
    """Partitions the range d[start..end] by the pivot, returns the pivot's final position.

    Invariant: d[start..i] is less than or equal to the pivot, d[i+1..j-1] is
    greater than the pivot.
    """
    pivot = d[end]
    i = start - 1
    for j in range(start, end):
        if d[j] <= pivot:
            i += 1
            d[i], d[j] = d[j], d[i]
    d[i + 1], d[end] = d[end], d[i + 1]
    return i + 1


example = [5, 2, 9, 1, 5, 6]
k = partition(example, 0, len(example) - 1)
print(k, example)          # 4 [5, 2, 1, 5, 6, 9]

The pivot value is 6; by the end of the operation it settles at index 4. No element larger than it remains to its left, and none smaller remains to its right. Partitioning uses $O(n)$ time and $O(1)$ extra space.

This is Lomuto partitioning; its code is short. Hoare partitioning advances from both ends toward the middle, performs fewer swaps, and is preferred in practice; in exchange, its boundary conditions are more delicate and it does not return the pivot’s exact position.

The Recursive Frame

def quicksort(array: list[int]) -> list[int]:
    d = list(array)

    def sort(start: int, end: int) -> None:
        if start >= end:                # base case: zero or one element
            return
        k = partition(d, start, end)
        sort(start, k - 1)
        sort(k + 1, end)                # the pivot (k) is in place; not reprocessed

    sort(0, len(d) - 1)
    return d


print(quicksort([5, 2, 9, 1, 5, 6]))     # [1, 2, 5, 5, 6, 9]
print(quicksort([]), quicksort([4]))    # [] [4]

Correctness comes from induction: after partitioning, the pivot is in its final position, and the two parts are independent of each other; if the parts are sorted correctly, the whole array is sorted.

The algorithm is in-place — the only extra space is the recursion stack — and not stable: swapping with distant elements disturbs the order of equal keys.

Cost and Pivot Choice

Cost depends on how balanced the partitioning is.

Balanced split. If the pivot lands in the middle every time, the recurrence is $T(n) = 2T(n/2) + O(n)$, and the result is $\Theta(n \log n)$.

Unbalanced split. If the pivot is the smallest or largest element every time, one part stays empty: $T(n) = T(n-1) + O(n)$, that is, $\Theta(n^2)$.

The second case is not merely theoretical. The implementation above, which chooses the last element as pivot, shows exactly this behavior on an already sorted array.

def partition_count(array: list[int]) -> int:
    """Total number of partitioning comparisons."""
    d, total = list(array), 0

    def sort(start: int, end: int) -> None:
        nonlocal total
        if start >= end:
            return
        total += end - start
        k = partition(d, start, end)
        sort(start, k - 1)
        sort(k + 1, end)

    sort(0, len(d) - 1)
    return total


n = 500
print(partition_count(list(range(n))))                    # 124750  — sorted: quadratic
print(partition_count([(i * 7919) % n for i in range(n)]))   # 5322  — balanced input

On sorted input, the number of comparisons is exactly equal to $n(n-1)/2$. On balanced input of the same size, the count drops by more than a factor of twenty.

The solution is to choose the pivot more carefully:

Choice	Input that triggers the worst case
First or last element	Sorted or reverse-sorted array
Middle element	A specially constructed array
Median of three (first, middle, last)	A specially constructed array
Random element	None — no input determines it

The first three are deterministic; a sufficiently informed adversary can always produce input that drives the algorithm into the quadratic case. With a random pivot, however, which element of the input will be chosen is not known, so the expected cost is $O(n \log n)$, and this rests on randomness, not on the input.

The reason the expected cost is linearithmic is that splits are usually reasonable: a random pivot falls into the middle half with probability about $1/2$, and such a split shrinks the problem size by at least three-quarters. Shrinking by a constant factor with constant probability means logarithmic depth.

Stack depth can also be controlled: if the smaller part is recursed into first and the larger part is handled with a loop, stack depth stays $O(\log n)$ even in the worst case.

Repeated Keys

If the array consists entirely of the same value, Lomuto partitioning puts every element into the less-than-or-equal region, and the split becomes unbalanced again. The solution is to split the array into three regions: smaller, equal, larger.

def three_way_sort(array: list[int]) -> list[int]:
    if len(array) <= 1:
        return list(array)
    pivot = array[len(array) // 2]
    smaller = [x for x in array if x < pivot]
    equal = [x for x in array if x == pivot]
    larger = [x for x in array if x > pivot]
    return three_way_sort(smaller) + equal + three_way_sort(larger)


print(three_way_sort([5, 2, 9, 1, 5, 6]))       # [1, 2, 5, 5, 6, 9]
print(three_way_sort([3, 3, 3, 3, 3]))          # [3, 3, 3, 3, 3]

The equal region is never processed again; on arrays with only a few distinct values, the cost approaches linear. The code here produces new lists for readability; an in-place three-way partitioning applies the same idea without extra space.

The Selection Problem

Partitioning’s second use is finding the kth smallest element without sorting the whole array. Since the pivot’s position is known after partitioning, the sought element can only be on one side; the other side is never processed.

def quickselect(array: list[int], k: int) -> int:
    """The kth smallest element (k starts from zero)."""
    d = list(array)
    start, end = 0, len(d) - 1
    while True:
        if start == end:
            return d[start]
        p = partition(d, start, end)
        if p == k:
            return d[p]
        if k < p:
            end = p - 1
        else:
            start = p + 1


data = [5, 2, 9, 1, 5, 6]
print(quickselect(data, 0), quickselect(data, 3), quickselect(data, 5))    # 1 5 9
print(sorted(data)[3])                                               # 5

The expected cost is $O(n)$: the problem size shrinks by a constant factor at every step, and the costs sum as $n + n/2 + n/4 + \dots < 2n$. Sorting and then reading the kth element would be $O(n \log n)$.

The same problem also has a solution whose worst case is linear too (“median of medians”), but its constant is large, and in practice random-pivot selection is preferred.

Summary

• Quicksort partitions by a pivot and requires no merge step; it operates in place and is not stable.
• Partitioning uses $O(n)$ time and $O(1)$ extra space; the pivot settles into its final position.
• Cost is $\Theta(n \log n)$ on a balanced split, $\Theta(n^2)$ on an unbalanced split.
• Deterministic pivot choices can be triggered by quadratic input; a random pivot makes the expected cost independent of the input.
• Three-way partitioning lowers the cost on repeated keys.
• The same partitioning finds the kth element at expected linear cost.

Next Step

Quicksort operates in place but has no worst-case guarantee; merge sort has the guarantee but needs extra space. The next lesson covers a third path that combines the two: heap sort, using the heap structure from the Data Structures course, operates in place and gives $O(n \log n)$ in every case.