Quick sort

Pivots and in-place partitioning, O(n log n) on average and O(n^2) at worst, and the four sorts compared.

A5.6Algorithms and complexityA level25 min

Quick sort is new at A level. Like merge sort it is divide and conquer, and on typical data it is one of the fastest sorts there is. Unlike merge sort it can sort in place, but it has a weakness: on the wrong data it slows right down to O(n²).

The idea

1. Choose one item to be the pivot.
2. Partition: move every item smaller than the pivot to its left and every item larger to its right. The pivot is now in its final place.
3. Quick sort the left part and the right part the same way. A part of 0 or 1 items is already sorted.

Compare the two divide and conquer sorts. Merge sort splits without looking and does its work combining the halves. Quick sort does its work dividing, with the partition, and has nothing left to do to combine: the parts are already in the right order either side of the pivot.

The shortest version builds new lists, which makes the idea plain but loses the in-place advantage:

def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[0]
    smaller = [x for x in items[1:] if x < pivot]
    larger = [x for x in items[1:] if x >= pivot]
    return quick_sort(smaller) + [pivot] + quick_sort(larger)

print(quick_sort([38, 12, 71, 45, 9, 83, 27, 60, 50]))

Run this in the simulator

Partitioning in place

Real implementations partition inside the list. There are several ways to do it, and an exam question will give or describe the one it wants. This one (the Lomuto scheme) takes the last item as the pivot and keeps an index i: everything to the left of i is smaller than the pivot. Each item that is smaller is swapped to position i, and i moves on. Finally the pivot is swapped into position i.

Partitioning [38, 12, 71, 45, 9, 83, 27, 60, 50] around the pivot 50:

50 is in its final place at index 5. Everything left of it is smaller and everything right of it is larger, though neither side is sorted yet. Quick sort now repeats on indexes 0 to 4 and 6 to 8.

In OCR's Exam Reference Language:

procedure quickSort(items, low, high)
    if low < high then
        p = partition(items, low, high)
        quickSort(items, low, p - 1)
        quickSort(items, p + 1, high)
    endif
endprocedure

function partition(items, low, high)
    pivot = items[high]
    i = low
    for j = low to high - 1
        if items[j] < pivot then
            temp = items[i]
            items[i] = items[j]
            items[j] = temp
            i = i + 1
        endif
    next j
    temp = items[i]
    items[i] = items[high]
    items[high] = temp
    return i
endfunction

Analysis

Partitioning a part of m items takes m - 1 comparisons: O(m). How much work quick sort does depends on how evenly the pivots split.

• Best and average case: O(n log n). If each pivot lands near the middle, the parts halve at every level, just like merge sort: about log₂ n levels, each partitioning n items in total. With pivots chosen from random data, the splits are uneven but good enough on average to keep O(n log n).
• Worst case: O(n²). If each pivot is the smallest or largest item, one part is empty and the other has only one item fewer. The partitions cost (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 comparisons. With the first or last item as pivot, this is exactly what happens to a list that is already sorted, or reversed.

def quick_sort_count(items, low, high):
    if low >= high:
        return 0
    pivot, i, count = items[high], low, 0
    for j in range(low, high):
        count = count + 1
        if items[j] < pivot:
            items[i], items[j] = items[j], items[i]
            i = i + 1
    items[i], items[high] = items[high], items[i]
    return count + quick_sort_count(items, low, i - 1) + quick_sort_count(items, i + 1, high)

import random
for n in [100, 200, 400]:
    shuffled = random.sample(range(n), n)
    in_order = list(range(n))
    print(n, "items: shuffled", quick_sort_count(shuffled, 0, n - 1),
          "comparisons, already sorted", quick_sort_count(in_order, 0, n - 1))

Run this in the simulator

Double n on shuffled data and the comparisons roughly double (a little more). Double n on sorted data and they multiply by 4. Choosing the pivot at random, or the middle item, makes the worst case very unlikely on real data, though still possible.

Space. Partitioning is in place, but the recursion is not free: every call waiting for its parts uses a stack frame. With even splits that is about log₂ n frames, O(log n); in the worst case it is n deep, O(n). Quick sort is not stable: the long-distance swaps can carry an item past an equal one.

The four sorts side by side

So which to use? Merge sort when you need a guaranteed O(n log n) or a stable sort; quick sort when memory is tight and the average case is what counts; insertion sort for small or nearly sorted lists. Real libraries mix them: Python's own sort combines merge sort with insertion sort for short runs.

Task: place the pivots

Write quick_sort(items, low, high) using the in-place partition from this lesson: the pivot is items[high], items strictly less than the pivot go to its left, and the function sorts the left part before the right part. It sorts items between indexes low and high inclusive, and returns the number of comparisons with a pivot that it made.

Each time a partition puts a pivot in its final place, print pivot <value> placed at index <index>. Parts of fewer than 2 items are not partitioned and print nothing. Then print, in this order:

• sorted: followed by readings after sorting
• readings: <n> comparisons
• ordered: <n> comparisons, sorting ordered, which is already in order (print no pivot lines for this one: give the function a way to switch printing off, such as a parameter show that defaults to True)

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

readings = [38, 12, 71, 45, 9, 83, 27, 60, 50]
ordered = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

def quick_sort(items, low, high):
    return 0

Challenges

1. Change the partition to use the middle item as the pivot (swap it to the end first). How many comparisons does the already sorted list take now?
2. Trace quick sort on [5, 5, 5, 5, 5]. What happens, and why is it slow?
3. Show with a list of (name, time) records that quick sort is not stable.