Sorting Algorithms in Depth

Quick sort

You know bubble sort, insertion sort and merge sort. Quick sort is the fourth sort in the specification, and the one most often used in practice. Like merge sort it is divide and conquer, but it does its work at a different moment.

1. Choose one item, the pivot.
2. Partition: put every item smaller than the pivot on its left, and every other item on its right. The pivot is now in its final position.
3. Sort the left part and the right part by calling quick sort on each, recursively.
4. A part of one item, or none, is already sorted, which is the base case.

Merge sort does the easy split and the hard merge. Quick sort does the hard split, the partition, and the merge is nothing at all.

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([6, 3, 9, 1, 8, 4]))

Partitioning [6, 3, 9, 1, 8, 4] around the first item gives [3, 1, 4] on the left, 6 in its place, and [9, 8] on the right. Each is then sorted in the same way.

Sorting in place

The version above builds new lists, which costs memory. The standard version rearranges the original list by swapping. It keeps a boundary that has everything smaller than the pivot on its left, and moves it along whenever it finds another small item.

def partition(items, low, high):
    pivot = items[high]                 # take the last item as the pivot
    boundary = low
    for i in range(low, high):
        if items[i] < pivot:
            items[i], items[boundary] = items[boundary], items[i]
            boundary += 1
    items[boundary], items[high] = items[high], items[boundary]
    return boundary                     # the pivot's final position

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

data = [6, 3, 9, 1, 8, 4]
print(partition(data, 0, 5), data)          # the pivot 4 goes to position 2
quick_sort_in_place(data)
print(data)

The pivot decides everything

If the pivot lands near the middle of the data, each part is half the size and there are about log n levels of recursion, each doing n work: O(n log n).

If it keeps landing at an end, one part is empty and the other has everything except the pivot. The recursion is n levels deep, and the work is n + (n - 1) + (n - 2) and so on, which is O(n²). That happens when the first item is the pivot and the data is already sorted, which is a very common input.

Counting the work

The claims above can be tested. This program counts the comparisons each of the four sorts makes on the same 200 numbers: in random order, already sorted, and in reverse order. The numbers come from a small formula rather than from random, so every run gives the same answer.

def pseudo_random_list(n, seed=12345):
    values = []
    x = seed
    for _ in range(n):
        x = (x * 1103515245 + 12345) % 2147483648
        values.append(x % 1000)
    return values

def bubble(items):
    items = items[:]
    n = len(items)
    comparisons = 0
    swapped = True
    passes = 0
    while swapped:
        swapped = False
        for i in range(n - 1 - passes):
            comparisons += 1
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        passes += 1
    return items, comparisons

def insertion(items):
    items = items[:]
    comparisons = 0
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if items[j] > current:
                items[j + 1] = items[j]
                j -= 1
            else:
                break
        items[j + 1] = current
    return items, comparisons

def merge_sort(items):
    comparisons = 0
    def sort(part):
        nonlocal comparisons
        if len(part) <= 1:
            return part
        middle = len(part) // 2
        left = sort(part[:middle])
        right = sort(part[middle:])
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            comparisons += 1
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged
    return sort(items), comparisons

def quick_sort(items):
    comparisons = 0
    def sort(part):
        nonlocal comparisons
        if len(part) <= 1:
            return part
        pivot = part[0]
        smaller = []
        larger = []
        for x in part[1:]:
            comparisons += 1
            if x < pivot:
                smaller.append(x)
            else:
                larger.append(x)
        return sort(smaller) + [pivot] + sort(larger)
    return sort(items), comparisons

numbers = pseudo_random_list(200)
cases = [("random", numbers), ("sorted", sorted(numbers)), ("reversed", sorted(numbers, reverse=True))]

print("comparisons".ljust(14) + "".join(name.ljust(10) for name, data in cases))
for label, sort in [("bubble", bubble), ("insertion", insertion), ("merge", merge_sort), ("quick", quick_sort)]:
    row = label.ljust(14)
    for name, data in cases:
        result, comparisons = sort(data)
        assert result == sorted(data)
        row += str(comparisons).ljust(10)
    print(row)

Read the table the program prints and compare it with the claims.

• Bubble and insertion sort need only 199 comparisons, n - 1, on a list that is already sorted: their best case is O(n). Their worst case is about n squared over two, 19 900.
• Merge sort hardly cares what order the data is in. It always splits and merges, so it is O(n log n) in every case. That consistency is its selling point.
• Quick sort is fastest on random data, and worst of all on sorted data, where it matches bubble sort's worst case. That is the pivot problem from the first section.

Choosing

Stability, and the sort you will actually use

A sort is stable if items that compare equal stay in their original order. It sounds minor and it is what makes sorting by two keys possible. Take people with a name and a grade, already in alphabetical order:

people = [("Asha", "B"), ("Ben", "A"), ("Chloe", "B"), ("Dev", "A")]

by_grade = sorted(people, key=lambda person: person[1])
print(by_grade)

The two A grades are still in alphabetical order, Ben before Dev, and so are the two Bs. A stable sort kept the earlier order among the ties, so sorting by grade did not undo sorting by name. An unstable sort is allowed to give Dev before Ben, and would, from time to time.

This gives the standard method for sorting on two keys: sort by the less important key first, then by the more important. Stability is what carries the first sort through the second.

people = [("Asha", "B"), ("Ben", "A"), ("Chloe", "B"), ("Dev", "A")]

people.sort(key=lambda person: person[0])         # first by name
people.sort(key=lambda person: person[1])         # then by grade; names stay in order
print(people)

print(sorted([3, 1, 2], reverse=True))
print(sorted(["pear", "fig", "banana"], key=len))

What Python does

Python's sorted and list.sort use Timsort, a hybrid of merge sort and insertion sort. It looks for stretches of the data that are already in order, called runs, and merges them. On random data it is O(n log n). On data that is already sorted it is O(n), because the whole list is one run. It is stable. In real programs, data is rarely random, and that is why Timsort is quick.

Searching a sorted list

Sorting pays for itself when you search the same data many times, because a binary search can be used. You wrote it with a loop. Here it is recursively, and with the library function bisect, which finds the position where a value is, or belongs, in a sorted list.

from bisect import bisect_left

def binary_search(items, target, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    if items[mid] < target:
        return binary_search(items, target, mid + 1, high)
    return binary_search(items, target, low, mid - 1)

data = [3, 8, 12, 17, 21, 25, 30, 36, 41]
print(binary_search(data, 25), binary_search(data, 26))
print(bisect_left(data, 25), bisect_left(data, 26))

bisect_left(data, 26) gives 6: the position where 26 would be inserted to keep the list sorted. A sorted list plus bisect is a way to find the nearest value, or to keep a list in order as items are added.

Key terms you must be able to define

Quick sort

A divide and conquer sort that partitions a list around a pivot and then sorts each part recursively.

Pivot

The item in quick sort that the others are compared with when the list is partitioned.

Partition

Rearranging a list so that items smaller than the pivot come before it and the others after it.

In-place sort

A sort that rearranges the items within the original list, using only a small amount of extra memory.

Stable sort

A sort that keeps equal items in the same relative order that they had before the sort.

Best case

The input of a given size for which an algorithm does the least work.

Worst case

The input of a given size for which an algorithm does the most work.

Divide and conquer

Solving a problem by dividing it into smaller copies of the same problem, solving them and combining the results.

Timsort

A stable hybrid of merge sort and insertion sort that exploits runs of ordered data, and is the sort used by Python.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

A Level sorting answers are about cases and trade offs, with the numbers to back them.

• Describe quick sort in the right order: choose a pivot, partition, sort the two parts recursively
• Give the best, average and worst case of each sort, and the input that causes the worst case
• Explain the quick sort worst case: the pivot is always the smallest or largest, so one part is empty
• Compare time and space together, as merge sort needs O(n) extra memory and quick sort does not
• Say what stable means, and why it matters when sorting on more than one key

Mistakes that cost marks here

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([6, 3, 9, 1, 8, 4]))