Quick Sort

Quick sort is another divide and conquer sort, and in practice it is one of the fastest. Instead of splitting the list in the middle and doing the hard work while merging, it does the hard work first: it picks one item, called the pivot, and moves everything smaller to its left and everything larger to its right. Then it sorts the two sides separately.

In this lesson you will write quick sort in a simple form and an in-place form, measure why its average case is fast but its worst case is slow, fix that with random pivots, and use its partition step to solve two more problems.

The idea in simple Python

Choose a pivot. Split the other items into three groups: less than the pivot, equal to it and greater than it. Sort the "less" and "greater" groups recursively, then join the three groups.

def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

fares = [450, 120, 890, 120, 300, 760, 55]
print(quick_sort(fares))

[55, 120, 120, 300, 450, 760, 890]

This version is easy to understand and correct, but it builds new lists at every level, so it uses O(n) extra memory. Real quick sort is valued because it sorts in place.

In-place partitioning

The Lomuto partition scheme uses the last item as the pivot and one boundary index store. Everything to the left of store is smaller than the pivot. Scanning from left to right, each item smaller than the pivot is swapped to the boundary and the boundary moves forward. Finally, the pivot is swapped into the boundary, which is its correct final position.

def partition(a, low, high):
    pivot = a[high]
    store = low
    for i in range(low, high):
        if a[i] < pivot:
            a[i], a[store] = a[store], a[i]
            store += 1
    a[store], a[high] = a[high], a[store]      # pivot to its final place
    return store

def quick_sort(a, low=0, high=None):
    if high is None:
        high = len(a) - 1
    if low < high:
        p = partition(a, low, high)
        print(f"pivot {a[p]:>2} placed at index {p}: {a}")
        quick_sort(a, low, p - 1)
        quick_sort(a, p + 1, high)

marks = [35, 81, 12, 67, 49, 90, 23, 58]
quick_sort(marks)
print(marks)

pivot 58 placed at index 4: [35, 12, 49, 23, 58, 90, 67, 81]
pivot 23 placed at index 1: [12, 23, 49, 35, 58, 90, 67, 81]
pivot 35 placed at index 2: [12, 23, 35, 49, 58, 90, 67, 81]
pivot 81 placed at index 6: [12, 23, 35, 49, 58, 67, 81, 90]
[12, 23, 35, 49, 58, 67, 81, 90]

After each partition, the pivot never moves again: it is already in its sorted position. Each partition step is O(n) for the part of the list it covers. The only extra memory is the recursion stack. There is also an older scheme by Tony Hoare, the inventor of quick sort, which uses two indexes moving towards each other and usually does fewer swaps.

Best, average and worst cases

How fast quick sort runs depends on the pivots:

• If each pivot lands near the middle, every split halves the problem, giving about log n levels of O(n) work: O(n log n).
• If each pivot is the smallest or largest item, one side is empty and the other has n - 1 items. That gives n levels: O(n²).

With "last item as pivot", the worst case happens on data that is already sorted, which is common in real life. Let us count comparisons:

import random

def quick_sort_count(a, choose_pivot):
    comparisons = 0
    def sort(low, high):
        nonlocal comparisons
        if low >= high:
            return
        k = choose_pivot(low, high)
        a[k], a[high] = a[high], a[k]          # move chosen pivot to the end
        pivot, store = a[high], low
        for i in range(low, high):
            comparisons += 1
            if a[i] < pivot:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[high] = a[high], a[store]
        sort(low, store - 1)
        sort(store + 1, high)
    sort(0, len(a) - 1)
    return comparisons

last = lambda low, high: high
rand = lambda low, high: random.randint(low, high)

random.seed(3)
n = 800
shuffled = random.sample(range(n), n)
print("random data, last pivot:  ", quick_sort_count(shuffled[:], last))
print("sorted data, last pivot:  ", quick_sort_count(list(range(n)), last))
print("sorted data, random pivot:", quick_sort_count(list(range(n)), rand))

random data, last pivot:   8487
sorted data, last pivot:   319600
sorted data, random pivot: 8229

On sorted data with the last item as pivot, quick sort made n(n - 1)/2 = 3,19,600 comparisons, the full O(n²). It also recursed 800 levels deep; with a few hundred more items it would hit Python's recursion limit. Choosing the pivot at random makes the bad case extremely unlikely for any input, bringing it back to about 8,200, as fast as on random data. Another common choice is the median of three: the middle value of the first, middle and last items.

Three-way partition

When the data has many duplicates, a two-way partition wastes work comparing equal items again and again. A three-way partition (also called the Dutch national flag method) splits the list into less-than, equal-to and greater-than parts in one pass. A delivery app that sorts orders by priority 0, 1 and 2 is the perfect case:

def three_way_partition(a, pivot):
    low, mid, high = 0, 0, len(a) - 1
    while mid <= high:
        if a[mid] < pivot:
            a[low], a[mid] = a[mid], a[low]
            low += 1
            mid += 1
        elif a[mid] > pivot:
            a[mid], a[high] = a[high], a[mid]
            high -= 1                     # do not move mid: check the swapped item
        else:
            mid += 1
    return a

priorities = [2, 0, 1, 2, 1, 0, 0, 2, 1]
print(three_way_partition(priorities, 1))

[0, 0, 0, 1, 1, 1, 2, 2, 2]

It sorts three kinds of values in a single O(n) pass with O(1) extra memory. Quick sort with a three-way partition handles lists full of repeated values in O(n log n) or better.

Advanced: quickselect

Sometimes you do not need the whole list sorted, only the item that would be at position k, such as the median salary in a company. Quickselect partitions once and then recurses into only the side that contains position k. On average it does O(n) work, because the sizes shrink n + n/2 + n/4 + ... which adds up to about 2n.

import random

def quickselect(a, k):
    """Return the k-th smallest item (k counts from 0)."""
    a = a[:]
    low, high = 0, len(a) - 1
    while True:
        r = random.randint(low, high)
        a[r], a[high] = a[high], a[r]
        pivot, store = a[high], low
        for i in range(low, high):
            if a[i] < pivot:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[high] = a[high], a[store]
        if store == k:
            return a[store]
        if k < store:
            high = store - 1
        else:
            low = store + 1

salaries = [42000, 35000, 98000, 51000, 28000, 64000, 47000]
print("Median salary:", quickselect(salaries, len(salaries) // 2))
print("Lowest:", quickselect(salaries, 0), "Highest:", quickselect(salaries, 6))

Median salary: 47000
Lowest: 28000 Highest: 98000

The answers are always correct; only the running time depends on the random pivots. Python's heapq.nsmallest() and statistics.median() solve similar tasks, and you will see heap-based selection in Heaps & Priority Queues.

Common mistakes

• Always using the first or last item as the pivot on data that may be sorted. Use a random pivot or median of three.
• Recursing on the pivot itself. Sort low..p-1 and p+1..high; including p can cause infinite recursion.
• Expecting stability. Quick sort can reorder equal items; use merge sort or sorted() when that matters.
• Moving mid after swapping with high in the three-way partition. The item that came from the back has not been checked yet.

Key points

• Quick sort partitions around a pivot, then sorts the two sides recursively.
• Lomuto partition uses the last item as pivot and places it in its final position in O(n).
• Average time is O(n log n); the worst case is O(n²) when pivots are always extremes, such as sorted input with a fixed pivot.
• Random or median-of-three pivots avoid the worst case in practice.
• Quick sort is in place (O(log n) stack on average) but not stable.
• Three-way partition handles duplicates; quickselect finds the k-th smallest in O(n) on average.

import random

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

def quick_sort(a, low=0, high=None):
    if high is None:
        high = len(a) - 1
    if low < high:
        p = partition(a, low, high)
        quick_sort(a, low, p - 1)
        quick_sort(a, p + 1, high)

def quickselect(a, k):
    a = a[:]
    low, high = 0, len(a) - 1
    while True:
        r = random.randint(low, high)
        a[r], a[high] = a[high], a[r]
        p = partition(a, low, high)
        if p == k:
            return a[p]
        if k < p:
            high = p - 1
        else:
            low = p + 1

times = [34, 18, 52, 27, 41, 18, 60, 25, 39]
third = quickselect(times, 2)
ordered = times[:]
quick_sort(ordered)
print(ordered)
print(third, third == ordered[2])

[18, 18, 25, 27, 34, 39, 41, 52, 60]
25 True