--- title: Quicksort source: 'https://academia.sh/en/courses/algorithms/quicksort' course: Algorithms language: en updated: '2026-08-17T18:07:44+00:00' license: 'CC BY-SA 4.0' --- # Quicksort In-place sorting with partitioning, the effect of pivot choice on the average and worst case, three-way partitioning, and selecting the kth element. 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. ```python 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 ```python 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. ```python 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. ```python 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. ```python 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.