Quicksort and partitioning

Quicksort is another divide and conquer sort, and many languages' sort functions have been built on it. Merge sort does its real work after the recursive calls, in the merge. Quicksort does it before them:

1. Pick one item, the pivot.
2. Partition the list: move the items smaller than the pivot before it, and the rest after it. The pivot is then in its final place, the place it has in the sorted list.
3. Sort the part before the pivot and the part after it, with a call of quicksort each. Nothing is left to combine.

Partitioning in place

The partition works inside the list itself, with no new lists. Here the pivot is the last item. The index i marks the end of the "smaller" part, so everything in values[low:i] is smaller than the pivot. j walks over the other items, and each smaller item it finds is swapped to position i, which grows the smaller part by one. At the end, the pivot is swapped into position i, between the two parts:

def partition(values, low, high):
    pivot = values[high]
    i = low
    for j in range(low, high):
        if values[j] < pivot:
            values[i], values[j] = values[j], values[i]
            i += 1
    values[i], values[high] = values[high], values[i]
    return i


values = [7, 2, 9, 4, 1, 8, 5]
p = partition(values, 0, len(values) - 1)
print(values, "pivot", values[p], "at index", p)

[2, 4, 1, 5, 9, 8, 7] pivot 5 at index 3

Neither side is sorted yet, but 5 is exactly where it belongs, with three smaller items before it and three bigger ones after. A partition looks at each item once, O(n), and needs no extra memory.

Sorting both sides

quicksort(values, low, high) sorts the items from values[low] to values[high]. A part with fewer than two items has nothing to sort. The pivot is left out of both calls: it's already in place, and leaving it out makes each call's part smaller, so the calls end. This version also returns how many comparisons it made, high - low for each partition:

import random


def partition(values, low, high):
    pivot = values[high]
    i = low
    for j in range(low, high):
        if values[j] < pivot:
            values[i], values[j] = values[j], values[i]
            i += 1
    values[i], values[high] = values[high], values[i]
    return i


def quicksort(values, low, high):
    if low >= high:
        return 0
    p = partition(values, low, high)
    comparisons = high - low
    comparisons += quicksort(values, low, p - 1)
    comparisons += quicksort(values, p + 1, high)
    return comparisons


values = list(range(500))
random.seed(1)
random.shuffle(values)
print(quicksort(values, 0, len(values) - 1), values[:5])
print(quicksort(values, 0, len(values) - 1), values[:5])

4751 [0, 1, 2, 3, 4]
124750 [0, 1, 2, 3, 4]

On shuffled values, the pivot usually lands somewhere near the middle, the parts roughly halve, and quicksort costs O(n log n) like merge sort. The second line sorts the same list again, now that it's sorted, and that is quicksort's worst case. The last item is the biggest, so each partition leaves all the other items on one side: n - 1 + n - 2 + ... comparisons, O(n²).

In Python there's a worse problem: each of those levels is one more nested call, and a sorted list of 2,000 values needs 2,000 of them, more than Python allows:

def partition(values, low, high):
    pivot = values[high]
    i = low
    for j in range(low, high):
        if values[j] < pivot:
            values[i], values[j] = values[j], values[i]
            i += 1
    values[i], values[high] = values[high], values[i]
    return i


def quicksort(values, low, high):
    if low < high:
        p = partition(values, low, high)
        quicksort(values, low, p - 1)
        quicksort(values, p + 1, high)


values = list(range(2000))
quicksort(values, 0, len(values) - 1)

Traceback (most recent call last):
  File "main.py", line 20, in <module>
    quicksort(values, 0, len(values) - 1)
    ~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 15, in quicksort
    quicksort(values, low, p - 1)
    ~~~~~~~~~^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 15, in quicksort
    quicksort(values, low, p - 1)
    ~~~~~~~~~^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 15, in quicksort
    quicksort(values, low, p - 1)
    ~~~~~~~~~^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 995 more times]
  File "main.py", line 14, in quicksort
    p = partition(values, low, high)
RecursionError: maximum recursion depth exceeded

A better pivot

The cure is a pivot that is unlikely to be the biggest or the smallest item. The middle item is a simple choice: swap it to the end first, then partition as before. On sorted and reversed data the middle item is the best pivot there is.

middle = (low + high) // 2
values[middle], values[high] = values[high], values[middle]

But the middle item has bad inputs too. In a list that rises and then falls, such as [0, 2, 4, 6, 5, 3, 1], the middle item is the biggest, and round after round the pivot stays one of the biggest items left: 3,000 such values still go about 1,500 calls deep, a RecursionError again. Data with a shape like that is not rare, so on structured data the middle pivot's O(n²) worst case can really happen.

A random item, random.randint(low, high) swapped to the end, is safer: no order of the items makes it slow every time, and seeding random keeps your runs repeatable. With a random pivot, quicksort is O(n log n) on average on any list of different values, and its calls stay a few dozen levels deep even for 200,000 values. The worst case is still O(n²), but now it's very unlikely. Quicksort needs no extra lists, but it isn't stable: a swap can jump an item past an equal one.

Many equal values

This two-way partition has one more weak spot, and no choice of pivot cures it: every item equal to the pivot goes to the same side. If all the items are equal, none is smaller than the pivot, so they all land on one side: the sorted case again, O(n²), and for a long list a RecursionError. A list with only a few different values has the same trouble. (Some two-way partitions, such as Hoare's, split the equal items between the two sides and avoid this, but they're harder to get right.) A three-way partition splits the items into three parts: smaller than the pivot, equal to it, and bigger. The equal part is finished, and only the other two need more sorting. It keeps three indexes: items before lt are smaller, items from lt up to i are equal, items after gt are bigger, and i walks through the unknown part between i and gt:

def partition3(values, pivot):
    lt = 0
    i = 0
    gt = len(values) - 1
    while i <= gt:
        if values[i] < pivot:
            values[lt], values[i] = values[i], values[lt]
            lt += 1
            i += 1
        elif values[i] > pivot:
            values[i], values[gt] = values[gt], values[i]
            gt -= 1
        else:
            i += 1
    return lt, gt


values = [3, 1, 3, 5, 3, 2, 5, 3]
print(partition3(values, 3), values)

(2, 5) [1, 2, 3, 3, 3, 3, 5, 5]

The result (2, 5) says that the 3s now fill indexes 2 to 5. When a bigger item is swapped to gt, i stays where it is: the item that came from the end hasn't been looked at yet. Each round either moves i on or moves gt back, so the partition is one pass, O(n).