Sorting Algorithms

Your phone shows contacts in alphabetical order. A shop shows prices from low to high. A search engine shows the best match first. Behind each of these is a sort, and behind every sort is a choice of method. Some methods take a second on a million items, and some take a day. This lesson builds the main methods by hand, counts what each one costs, and ends with the one you will actually use.

Learning Objectives

After this lesson, you will be able to:

Say what stable and in place mean, and tell which sorts have each property
Trace bubble, selection and insertion sort by hand, and explain why insertion sort is fast on nearly sorted data
Write merge sort and quick sort, and explain why the first is always O(n log n) and the second is not
Explain with a decision tree why no comparison sort can beat n log n
Write counting sort and radix sort, and say when they win
Use sorted, list.sort, key= and reverse= correctly, and choose the right sort for a job

Prerequisites

Before You Start

Review

This lesson uses recursion, the idea you met in the recursion lesson: a function that calls itself on a smaller piece of the problem. Merge sort and quick sort both rest on it.

#Why Sort at All

Picture a shelf of books in no order. To find one title you must check every book. Put them in alphabetical order and you can open the shelf in the middle and halve the search, as in the binary search you already know.

Sorting pays off in four ways.

Searching gets cheap. Binary search needs sorted data.
Equal items end up side by side, so finding duplicates is one pass.
The smallest, the largest, the median and the top few sit at known places.
Two sorted lists can be merged into one in a single pass.

pythonrunnable cell

scores = [72, 91, 65, 88, 91]
ordered = sorted(scores)
print(ordered)
print("lowest:", ordered[0], "highest:", ordered[-1], "median:", ordered[len(ordered) // 2])
print("has a duplicate:", any(a == b for a, b in zip(ordered, ordered[1:])))
# Output:
# [65, 72, 88, 91, 91]
# lowest: 65 highest: 91 median: 88
# has a duplicate: True

One sort answered four questions. The question for the rest of the lesson is what that sort costs, and how to do it cheaply.

#Words You Need Before the Sorts

Three words come up for every sort, so here they are in plain language.

A comparison sort learns about the items only by asking one question: does this item come before that one? Bubble, selection, insertion, merge, quick, heap and Python's own sort are all comparison sorts. Counting sort and radix sort, later in the lesson, are not.

A sort is stable if items that compare equal keep the order they had before. Say two students both scored 3, Ana first in the list and Eli second. A stable sort by score keeps Ana before Eli. This matters when you sort twice: first by name, then by score, and you want the names to stay in order inside each score.

A sort is in place if it rearranges the list it was given and needs only a small, fixed amount of extra memory. Extra memory beyond the input is called extra space. A sort that builds a whole second list is not in place.

pythonrunnable cell

rows = [("Ana", 3), ("Raj", 1), ("Eli", 3), ("Zed", 1)]
print(sorted(rows, key=lambda row: row[1]))

data = [3, 1, 2]
print(sorted(data), data)      # a new list, the old one is untouched
data.sort()                    # in place: no new list is made
print(data)
# Output:
# [('Raj', 1), ('Zed', 1), ('Ana', 3), ('Eli', 3)]
# [1, 2, 3] [3, 1, 2]
# [1, 2, 3]

Raj stays before Zed and Ana stays before Eli, because they tied. We count cost in comparisons and in extra space. The worst case is the input that makes a sort work hardest, and the average case is a typical input, as in the start-here lesson.

#Three Simple Sorts: Bubble, Selection, Insertion

Start with the three methods you could invent in an afternoon. Each one is O(n²) in the typical case, which means doubling the list roughly quadruples the work. Trace each on a tiny list first.

Bubble sort sweeps through the list and swaps any neighbours that are out of order. Each sweep carries the largest remaining item to the end, like a bubble rising. It stops after a sweep with no swaps. Take 5, 1, 4, 2.

Sweep	Comparisons made	List afterwards
1	5 and 1 swap, 5 and 4 swap, 5 and 2 swap	1, 4, 2, 5
2	1 and 4 stay, 4 and 2 swap	1, 2, 4, 5
3	1 and 2 stay, no swap, so stop	1, 2, 4, 5

Selection sort finds the smallest item in the unsorted part and swaps it to the front of that part. Take 29, 10, 14, 37, 13. The bar marks where the sorted part ends.

Round	Smallest in the rest	List afterwards
1	10	10 \| 29, 14, 37, 13
2	13	10, 13 \| 14, 37, 29
3	14, already in place	10, 13, 14 \| 37, 29
4	29	10, 13, 14, 29, 37

Selection sort always scans everything that is left, so it makes 4 + 3 + 2 + 1 = 10 comparisons here whatever the order. For n items that is n(n-1)/2 comparisons every time.

Insertion sort keeps a sorted part at the front and slides each new item left into its place, like sorting playing cards in your hand. Take 5, 2, 4, 6, 1, 3.

Take	Slides past	List afterwards
2	5	2, 5 \| 4, 6, 1, 3
4	5	2, 4, 5 \| 6, 1, 3
6	nothing	2, 4, 5, 6 \| 1, 3
1	6, 5, 4, 2	1, 2, 4, 5, 6 \| 3
3	6, 5, 4	1, 2, 3, 4, 5, 6

Notice the card 6. It looked at its left neighbour once, found it smaller, and stopped.

What Do You Think?

Insertion sort runs on the list 1, 2, 3, 4, 5, 6, which is already sorted. How many comparisons does it make in total?

Watch the simple sorts raceInteractive

Pick bubble, selection or insertion sort, press play, and compare the counters as the list grows. Then try the others.

Loading visualization...

Now count. The cell sorts the same random lists with all three and reports comparisons, then tries a nearly sorted list and a sorted one.

pythonrunnable cell

import random


def bubble_sort(a):
    """Sort the list in place. Return the number of comparisons."""
    comparisons = 0
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for i in range(end):
            comparisons += 1
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return comparisons


def selection_sort(a):
    """Sort the list in place. Return the number of comparisons."""
    comparisons = 0
    for start in range(len(a) - 1):
        smallest = start
        for i in range(start + 1, len(a)):
            comparisons += 1
            if a[i] < a[smallest]:
                smallest = i
        a[start], a[smallest] = a[smallest], a[start]
    return comparisons


def insertion_sort(a):
    """Sort the list in place. Return the number of comparisons."""
    comparisons = 0
    for i in range(1, len(a)):
        current = a[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if a[j] > current:
                a[j + 1] = a[j]        # shift the bigger item one position right
                j -= 1
            else:
                break
        a[j + 1] = current
    return comparisons


def counts(values):
    return [sort(list(values)) for sort in (bubble_sort, selection_sort, insertion_sort)]


random.seed(7)
for n in (100, 200, 400):
    values = random.sample(range(10 * n), n)
    print(f"n={n}: bubble, selection, insertion = {counts(values)}")

nearly = list(range(400))
nearly[10], nearly[11] = nearly[11], nearly[10]       # one neighbouring pair swapped
print("nearly sorted, n=400:", counts(nearly))
print("already sorted, n=400:", counts(range(400)))
# Output:
# n=100: bubble, selection, insertion = [4674, 4950, 2232]
# n=200: bubble, selection, insertion = [19885, 19900, 10819]
# n=400: bubble, selection, insertion = [79734, 79800, 43937]
# nearly sorted, n=400: [797, 79800, 400]
# already sorted, n=400: [399, 79800, 399]

Each time n doubles, every count grows about four times. That is O(n²). Selection sort is exactly n(n-1)/2, and 400 × 399 / 2 is 79,800.

The last two lines show the one strength of insertion sort. An inversion is a pair of items in the wrong order, such as a 5 sitting before a 2. Insertion sort makes at most one comparison per item plus one more per inversion. A nearly sorted list has few inversions, so the cost is close to n. That is why Python's own sort uses insertion sort on short stretches.

The costs follow from the traces. Bubble sort is O(n) on sorted input, because one sweep with no swap stops it, and O(n²) otherwise. Selection sort is O(n²) always, because it scans the rest every round. Insertion sort is O(n) on nearly sorted input and O(n²) on a reversed list, where every item slides all the way. None of them builds a second list, so each needs O(1) extra space.

All three are in place. Bubble and insertion sort are stable because they move an item only past a strictly bigger one. Selection sort is not stable, because its swap can throw an item far over a tied one.

pythonrunnable cell

people = [("a", 2), ("b", 2), ("c", 1)]
by_swap = list(people)
# selection sort on the score, written with the usual swap
for start in range(len(by_swap) - 1):
    smallest = start
    for i in range(start + 1, len(by_swap)):
        if by_swap[i][1] < by_swap[smallest][1]:
            smallest = i
    by_swap[start], by_swap[smallest] = by_swap[smallest], by_swap[start]
print(by_swap)
print(sorted(people, key=lambda p: p[1]))
# Output:
# [('c', 1), ('b', 2), ('a', 2)]
# [('c', 1), ('a', 2), ('b', 2)]

The swap moved a from the front to the back, behind its twin b. Python's stable sort kept a first.

#Merge Sort: Halve, Sort, Merge

To beat O(n²), stop comparing everything with everything. Merge sort uses a recursive idea. Split the list in half. Sort each half by calling the same function on it. Then merge the two sorted halves, which means to join them into one sorted list. A list of one item is already sorted, and that is the base case that stops the recursion.

Here is the splitting for eight items, then the merging back.

text

split:   [6 3 8 1 7 2 5 4]
         [6 3 8 1] [7 2 5 4]
         [6 3] [8 1] [7 2] [5 4]
         [6] [3] [8] [1] [7] [2] [5] [4]
merge:   [3 6] [1 8] [2 7] [4 5]
         [1 3 6 8] [2 4 5 7]
         [1 2 3 4 5 6 7 8]

The merge is the clever part. Keep a finger at the front of each sorted half, take the smaller of the two front items, and move that finger. Merge 1, 3, 6, 8 with 2, 4, 5, 7.

Fronts compared	Taken	Output so far
1 and 2	1	1
3 and 2	2	1, 2
3 and 4	3	1, 2, 3
6 and 4	4	1, 2, 3, 4
6 and 5	5	1, 2, 3, 4, 5
6 and 7	6	1, 2, 3, 4, 5, 6
8 and 7	7	1, 2, 3, 4, 5, 6, 7
the left half still has 8	8	1, 2, 3, 4, 5, 6, 7, 8

Eight items took 7 comparisons. Merging two lists of total size m takes at most m - 1 comparisons, so one merge is a single pass.

Merge sort: split the list, then merge the halvesInteractive

Eight numbers split into three levels. Each level is merged back in one pass.

Loading visualization...

pythonrunnable cell

import math
import random


def merge(left, right):
    """Join two sorted lists into one sorted list. Return it and the comparison count."""
    merged = []
    i = j = comparisons = 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:          # <= takes the left item on a tie: this keeps the sort stable
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])              # one side is empty: copy what is left of the other
    merged.extend(right[j:])
    return merged, comparisons


def merge_sort(items):
    """Return a new sorted list and the number of comparisons."""
    if len(items) <= 1:                  # base case: 0 or 1 items are already sorted
        return list(items), 0
    middle = len(items) // 2
    left, left_count = merge_sort(items[:middle])
    right, right_count = merge_sort(items[middle:])
    merged, merge_count = merge(left, right)
    return merged, left_count + right_count + merge_count


print(merge([1, 3, 6, 8], [2, 4, 5, 7]))

random.seed(7)
for n in (100, 200, 400, 800):
    values = [random.random() for _ in range(n)]
    result, count = merge_sort(values)
    bound = math.ceil(n * math.log2(n))
    print(f"n={n}: {count} comparisons, n*log2(n) = {bound}, correct = {result == sorted(values)}")
# Output:
# ([1, 2, 3, 4, 5, 6, 7, 8], 7)
# n=100: 543 comparisons, n*log2(n) = 665, correct = True
# n=200: 1264 comparisons, n*log2(n) = 1529, correct = True
# n=400: 2960 comparisons, n*log2(n) = 3458, correct = True
# n=800: 6712 comparisons, n*log2(n) = 7716, correct = True

Why O(n log n)? Halving 8 items takes 3 levels, and halving n items takes about log2 n levels. At each level the merges together touch every item once, which costs at most n comparisons. So the total is at most n times log2 n, and the last column shows the counts stay under that line.

Merge sort has no bad input, so its worst case is O(n log n) too. It pays in memory: the merged lists are new, so it needs O(n) extra space. The recursion is only about log n calls deep, so it never meets Python's recursion limit. The <= in the merge makes it stable.

Use merge sort when you need a stable O(n log n) guarantee, when sorting linked lists, or when the data is too big for memory and you merge sorted pieces from disk.

#Quick Sort: Partition Around a Pivot

Quick sort also splits the work, but it splits by value, not by position. It picks one item, the pivot. It then partitions the list, which means moving every smaller item to one side of the pivot and every larger item to the other. After that the pivot is in its final place. Sort each side the same way.

Here is one partition with the last item as the pivot. A boundary marks the end of the group of items smaller than the pivot. Each time we meet a smaller item we swap it to the boundary and move the boundary one step.

pythonrunnable cell

def partition(a, low, high):
    """Partition a[low..high] around the last item. Return the pivot's final index."""
    pivot = a[high]
    boundary = low                       # a[low:boundary] holds the items smaller than the pivot
    for j in range(low, high):
        if a[j] < pivot:
            a[boundary], a[j] = a[j], a[boundary]
            boundary += 1
        print(f"  j={j}  {a}  boundary={boundary}")
    a[boundary], a[high] = a[high], a[boundary]   # drop the pivot between the two groups
    return boundary


items = [7, 2, 9, 4, 3, 8, 6]
print("start", items, " pivot = 6")
spot = partition(items, 0, len(items) - 1)
print("end  ", items, " pivot sits at index", spot)
# Output:
# start [7, 2, 9, 4, 3, 8, 6]  pivot = 6
#   j=0  [7, 2, 9, 4, 3, 8, 6]  boundary=0
#   j=1  [2, 7, 9, 4, 3, 8, 6]  boundary=1
#   j=2  [2, 7, 9, 4, 3, 8, 6]  boundary=1
#   j=3  [2, 4, 9, 7, 3, 8, 6]  boundary=2
#   j=4  [2, 4, 3, 7, 9, 8, 6]  boundary=3
#   j=5  [2, 4, 3, 7, 9, 8, 6]  boundary=3
# end   [2, 4, 3, 6, 9, 8, 7]  pivot sits at index 3

Read the last line. Everything left of the 6 is smaller, everything right is larger, and the 6 will never move again. Quick sort now handles [2, 4, 3] and [9, 8, 7] the same way. One partition is a single pass, so it costs n - 1 comparisons.

The quality of the pivot decides everything. A pivot near the middle splits the list into two halves, and the cost is O(n log n), like merge sort. A pivot that is always the smallest or largest item leaves one side empty and the other side holding everything else.

What Do You Think?

Quick sort always takes the last item as the pivot, and you give it a list of 400 numbers that is already sorted from small to large. About how many comparisons does it make?

Quick sort: pick a pivot, split around itInteractive

Run the random list first. Then switch to the sorted preset and watch one side stay empty.

Loading visualization...

The next cell is a full in-place quick sort that counts comparisons. It can use the last item or a random item as the pivot. It always recurses into the smaller side and loops on the bigger side, which keeps the call stack at O(log n) levels even when a split is bad.

pythonrunnable cell

import random


def quick_sort(a, pivot_rule="last", rng=None):
    """Sort the list in place. Return the number of comparisons."""
    comparisons = 0

    def sort(low, high):
        nonlocal comparisons
        while low < high:
            if pivot_rule == "random":
                pick = rng.randint(low, high)
                a[pick], a[high] = a[high], a[pick]      # move the random pick to the end
            pivot = a[high]
            boundary = low
            for j in range(low, high):
                comparisons += 1
                if a[j] < pivot:
                    a[boundary], a[j] = a[j], a[boundary]
                    boundary += 1
            a[boundary], a[high] = a[high], a[boundary]
            if boundary - low < high - boundary:         # recurse into the smaller side,
                sort(low, boundary - 1)                  # loop on the bigger side
                low = boundary + 1
            else:
                sort(boundary + 1, high)
                high = boundary - 1

    sort(0, len(a) - 1)
    return comparisons


n = 400
random.seed(3)
shuffled = random.sample(range(n), n)
inputs = {"shuffled": shuffled, "already sorted": list(range(n)), "all equal": [5] * n}
for name, data in inputs.items():
    last = quick_sort(list(data))
    rand = quick_sort(list(data), "random", random.Random(1))
    print(f"{name:<15} last-item pivot: {last:>6}   random pivot: {rand:>6}")
print("n*(n-1)/2 =", n * (n - 1) // 2)
# Output:
# shuffled        last-item pivot:   3181   random pivot:   3571
# already sorted  last-item pivot:  79800   random pivot:   3716
# all equal       last-item pivot:  79800   random pivot:  79800
# n*(n-1)/2 = 79800

Three facts fall out of this table.

On shuffled data both rules are near n log n, which is 3,458 for n = 400. That is the average case.
A random pivot has no bad input. No one can build a list that is always slow for it, because the pivot is chosen by chance. A worst case still exists, but it needs terrible luck. Taking the median of the first, middle and last items is another popular rule.
A list of all equal items beats both rules. The test a[j] < pivot is never true, so one side is always empty.

Why is the average still O(n log n) when splits are uneven? Even if every split put just one tenth of the items on the small side, the list would shrink to size 1 in a number of levels that is still proportional to log n, only with a bigger constant. Only a split that is almost always empty breaks it.

Equal items need a fix: split into three groups, smaller, equal and larger, and finish all the equal ones at once. The in-place form of this is known as the Dutch national flag partition. The short form below builds new lists to show the idea.

pythonrunnable cell

import random


def quick_sort_3way(items, rng):
    """Return a new sorted list. Three groups: smaller, equal, larger."""
    if len(items) <= 1:
        return list(items)
    pivot = items[rng.randrange(len(items))]
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]       # every copy of the pivot is finished at once
    larger = [x for x in items if x > pivot]
    return quick_sort_3way(smaller, rng) + equal + quick_sort_3way(larger, rng)


rng = random.Random(1)
print(quick_sort_3way([5] * 400, rng) == [5] * 400)        # one pass, then done
data = rng.sample(range(1000), 1000)
print(quick_sort_3way(data, rng) == sorted(data))
# Output:
# True
# True

Summing up quick sort: average O(n log n), worst case O(n²), and O(log n) extra space for the call stack with the smaller-side rule. It is in place but not stable, because the swaps jump over equal items. In practice it is fast because it works inside the list and touches memory in order.

#Why Comparison Sorts Cannot Beat n log n

Can a cleverer comparison sort do better than n log n? No, and you can see why with a game of yes or no questions.

A comparison is a yes or no question. Three items a, b and c can be in 6 different orders. After one question the answers split the 6 orders into two groups at best, after two questions into four groups, after k questions into at most 2^k groups. To pick out one order for certain you need 2^k to be at least 6, so k is at least 3. Three comparisons are needed in the worst case.

Draw every possible run of questions and you get a decision tree: each fork is a comparison, and each leaf is one finished order. A tree with k levels has at most 2^k leaves. For n items there are n! (n factorial, 1 × 2 × ... × n) orders, so the tree needs at least n! leaves, and some run must be at least log2(n!) questions long.

pythonrunnable cell

import math

print("n      orders (n!)        yes/no questions needed")
for n in (3, 5, 10, 100, 1000):
    orders = math.factorial(n)
    questions = (orders - 1).bit_length()          # the smallest k with 2**k >= n!
    shown = f"{orders:,}" if n <= 10 else f"{len(str(orders))} digits"
    print(f"{n:<6} {shown:<18} {questions}")
# Output:
# n      orders (n!)        yes/no questions needed
# 3      6                  3
# 5      120                7
# 10     3,628,800          22
# 100    158 digits         525
# 1000   2568 digits        8530

Is log2(n!) really about n log2 n? Half of the factors in n! are at least n/2, so n! is at least (n/2) multiplied by itself n/2 times, and its log2 is at least (n/2) × log2(n/2). That grows like n log n. So every comparison sort needs at least about n log n comparisons in the worst case. Computer scientists write this as Ω(n log n), with the Greek letter omega for "at least".

The bound is tight. For 800 items it says 6,568 comparisons are unavoidable in the worst case, and our merge sort used 6,712 on a random list. To go faster you must stop using only comparisons.

#Beating n log n: Counting Sort and Radix Sort

The limit holds for sorts that only compare. If the items are whole numbers in a small range, you can use the numbers themselves as positions in a list.

Counting sort counts how many times each value appears, then writes the values out in order. Take 2, 5, 3, 0, 2, 3, 0, 3, with values from 0 to 5. The counts list has one position per value: two 0s, no 1s, two 2s, three 3s, no 4s, one 5. Write 0 twice, 2 twice, 3 three times, and 5 once.

pythonrunnable cell

def counting_sort(values, k):
    """Sort whole numbers in range(k). Time O(n + k), extra space O(k)."""
    counts = [0] * k
    for v in values:
        counts[v] += 1                       # one pass: count each value
    result = []
    for v in range(k):
        result.extend([v] * counts[v])       # one pass over the counts: write each value back
    return result, counts


values = [2, 5, 3, 0, 2, 3, 0, 3]
print(counting_sort(values, 6))
# Output:
# ([0, 0, 2, 2, 3, 3, 3, 5], [2, 0, 2, 3, 0, 1])

There are two passes, one over the n values and one over the k counts, so the time is O(n + k). When k is small, say exam marks from 0 to 100, that is O(n), and sorting a million marks needs no comparisons at all. The weak spot is a big range. Ten numbers that can reach a billion would need a counts list of a billion positions.

Radix sort handles bigger numbers by sorting one digit at a time, starting from the ones digit. Each pass uses a counting sort that is stable. Stability is the whole trick: when you sort by the tens digit, numbers with the same tens digit stay in the order the ones digit gave them. Take 170, 45, 75, 90, 802, 24, 2, 66.

pythonrunnable cell

def counting_sort_by(items, digit_of, k):
    """Stable counting sort of items by a small whole-number key in range(k)."""
    counts = [0] * k
    for item in items:
        counts[digit_of(item)] += 1
    start = [0] * k                          # start[d] = where the first item with key d goes
    for d in range(1, k):
        start[d] = start[d - 1] + counts[d - 1]
    result = [None] * len(items)
    for item in items:                       # walk left to right so equal keys keep their order
        d = digit_of(item)
        result[start[d]] = item
        start[d] += 1
    return result


def radix_sort(numbers):
    """Sort non-negative whole numbers, one decimal digit at a time, ones digit first."""
    place = 1
    biggest = max(numbers)
    while place <= biggest:
        numbers = counting_sort_by(numbers, lambda x: (x // place) % 10, 10)
        print(f"after the {place}s digit:", numbers)
        place *= 10
    return numbers


radix_sort([170, 45, 75, 90, 802, 24, 2, 66])
# Output:
# after the 1s digit: [170, 90, 802, 2, 24, 45, 75, 66]
# after the 10s digit: [802, 2, 24, 45, 66, 170, 75, 90]
# after the 100s digit: [2, 24, 45, 66, 75, 90, 170, 802]

With d digits and base b (here 10), radix sort makes d passes of O(n + b) each, so its time is O(d × (n + b)) and its extra space is O(n + b). If d stays small, that is linear in n. It suits fixed-width keys such as ages, postcodes and dates.

In everyday Python, sorted is written in compiled C and these two are not, so for most lists sorted still wins. Counting and radix sort matter for the idea they teach, for interviews, and for huge lists with a small range, where a counting step such as np.bincount in NumPy is the fast tool.

#Python's sorted and Timsort

Python's built-in sort is called Timsort. Tim Peters designed it for Python in 2002. It is a hybrid. It scans the list for runs, which are stretches already in order, either rising or strictly falling. It lengthens short runs with insertion sort, then merges runs the way merge sort does, with rules that keep the merges balanced.

Its promises are the ones you want. It is stable. Its worst case is O(n log n). It needs O(n) extra space. And on data that is already sorted it makes only n - 1 comparisons, so real data that is partly in order, such as log lines in time order, sorts fast. A counting class proves it, because Python sorts using only the less-than operator.

pythonrunnable cell

import random


class Counted:
    """A number that counts every time it is compared with <."""
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.comparisons += 1
        return self.value < other.value


def comparisons_to_sort(values):
    Counted.comparisons = 0
    sorted(Counted(v) for v in values)
    return Counted.comparisons


random.seed(1)
shuffled = random.sample(range(1000), 1000)
print("already sorted:", comparisons_to_sort(sorted(shuffled)))
print("reversed:      ", comparisons_to_sort(sorted(shuffled, reverse=True)))
print("shuffled is more:", comparisons_to_sort(shuffled) > 5000)
# Output:
# already sorted: 999
# reversed:       999
# shuffled is more: True

A sorted list and a reversed list both cost 999 comparisons for 1,000 items, because each is one long run. The exact count for a shuffled list depends on the Python version, so the cell tests only that it is much larger.

You use two spellings. sorted(x) returns a new list and accepts any iterable. x.sort() sorts a list in place and returns None. Both take two options. key= is a function that turns each item into the value to sort by, called once per item. reverse=True sorts from large to small, and ties still keep their original order.

What Do You Think?

What does this print? rows = [("ada", 3), ("bo", 1), ("cy", 3)] print(sorted(rows, key=lambda r: r[1], reverse=True))

A few keys cover most needs.

pythonrunnable cell

from operator import itemgetter

rows = [("ada", 0.91), ("bo", 0.85), ("cy", 0.91), ("di", 0.85), ("ed", 0.97)]
print(sorted(rows, key=itemgetter(1), reverse=True))                 # ties keep their input order
print(sorted(rows, key=lambda r: (-r[1], r[0])))                     # score high to low, then name

words = ["Zebra", "apple", "Mango", "banana"]
print(sorted(words))                                                 # capitals sort before lowercase
print(sorted(words, key=str.lower))
print(sorted(words, key=len))                                        # ties keep their input order

ranked = sorted(rows, key=lambda r: r[0])                            # sort by the tie-break first
ranked = sorted(ranked, key=lambda r: r[1], reverse=True)            # then by the main key
print(ranked == sorted(rows, key=lambda r: (-r[1], r[0])))
# Output:
# [('ed', 0.97), ('ada', 0.91), ('cy', 0.91), ('bo', 0.85), ('di', 0.85)]
# [('ed', 0.97), ('ada', 0.91), ('cy', 0.91), ('bo', 0.85), ('di', 0.85)]
# ['Mango', 'Zebra', 'apple', 'banana']
# ['apple', 'banana', 'Mango', 'Zebra']
# ['Zebra', 'apple', 'Mango', 'banana']
# True

A tuple key compares its parts in order, so (-score, name) means "score high to low, then name". For two keys you can also sort twice, but the order of the passes matters: the tie-break goes first and the main key goes last. This is stability put to work.

#Heap Sort in One Paragraph

A heap is a structure that always keeps the smallest item easy to reach. Heap sort builds a heap from the list, then removes the smallest item again and again. Building takes O(n), and each of the n removals costs O(log n), so the total is O(n log n) in every case, with no bad input.

The array version works inside the list and needs O(1) extra space. It is not stable, and it jumps around in memory, which is why quick sort is usually faster in practice.

pythonrunnable cell

import heapq


def heap_sort(items):
    """Build a heap in O(n), then pop the smallest item n times at O(log n) each."""
    heap = list(items)
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]


print(heap_sort([5, 2, 9, 1, 7, 3]))
# Output:
# [1, 2, 3, 5, 7, 9]

This copy version uses O(n) extra space. The heaps lesson, Heaps and Priority Queues, shows how a heap works inside. Heaps matter for more than sorting: when you need only the k smallest items, a heap that holds just k of them avoids a full sort.

#Choosing a Sort

Here is every sort in one table. "Extra space" counts memory beyond the list itself.

Sort	Best	Average	Worst	Extra space	Stable
Bubble	O(n)	O(n²)	O(n²)	O(1)	yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	no
Insertion	O(n)	O(n²)	O(n²)	O(1)	yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	yes
Quick, random pivot	O(n log n)	O(n log n)	O(n²)	O(log n)	no
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	no
Counting	O(n + k)	O(n + k)	O(n + k)	O(n + k)	yes, when written stably
Radix	O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	yes
Timsort	O(n)	O(n log n)	O(n log n)	O(n)	yes

Here is how to choose.

Default to sorted or list.sort. It is stable, handles partly sorted data well, and runs in C.
Need only the smallest or largest? Use min or max, one pass of n - 1 comparisons. Sorting a list to read its first item does far more work.
Need only the k best? A heap of size k beats a full sort when k is small.
Keys are small whole numbers? Counting sort is O(n + k), and radix sort handles fixed-width keys.
Will you search the data many times? Sort once, then use bisect for each lookup.
Writing your own because memory is tight or the interviewer asks? Quick sort with a random pivot works in place. Heap sort works in place with a firm O(n log n) bound. Merge sort is the stable choice.

#How Sorting Shows Up in ML

Three jobs in ML code are sorting in disguise. Ranking sorts documents or predictions by score. K-nearest neighbours sorts distances to find the closest rows. Drawing an ROC curve sorts predictions by score and then moves a threshold down the sorted list. For the top few, a full sort wastes work, and NumPy offers np.argsort for the full order and np.argpartition for just the top k.

pythonrunnable cell

scores = [0.12, 0.88, 0.45, 0.91, 0.30, 0.77]

order = sorted(range(len(scores)), key=lambda i: scores[i], reverse=True)   # a pure Python "argsort"
print(order)
print("top 3 documents:", order[:3], [scores[i] for i in order[:3]])
# Output:
# [3, 1, 5, 2, 4, 0]
# top 3 documents: [3, 1, 5] [0.91, 0.88, 0.77]

Sorting the positions, not the scores, tells you which documents won, and that is what argsort returns.

#Common Mistakes

Watch Out

Using the result of list.sort()

Fix: Call scores.sort() on its own line, or write ranked = sorted(scores) to get a new list.

pythonrunnable cell

scores = [0.62, 0.91, 0.55]
ranked = scores.sort(reverse=True)
print(ranked, scores)
# Output:
# None [0.91, 0.62, 0.55]

list.sort() changes the list and returns None, as a signal that nothing new was made. Code such as scores.sort()[:3] then fails with a TypeError, and ranked holds nothing.

Watch Out

Sorting data that holds None

Fix: Say where missing values go, inside the key function, or remove them first.

pythonrunnable cell

scores = [0.9, None, 0.4, 0.7]
try:
    sorted(scores)
except TypeError as error:
    print(error)

print(sorted(scores, key=lambda s: float("-inf") if s is None else s))
# Output:
# '<' not supported between instances of 'NoneType' and 'float'
# [None, 0.4, 0.7, 0.9]

Sorting only needs the less-than test, and Python refuses to compare None with a number. Missing values are common in real data, so give the key a rule.

Watch Out

Sorting by two keys in the wrong order

Fix: With two stable sorts, sort by the tie-break first and by the main key last. Or use one sort with a tuple key.

pythonrunnable cell

rows = [("kim", 0.7), ("al", 0.9), ("bea", 0.7), ("cy", 0.9)]
wrong = sorted(sorted(rows, key=lambda r: r[1], reverse=True), key=lambda r: r[0])
right = sorted(sorted(rows, key=lambda r: r[0]), key=lambda r: r[1], reverse=True)
print(wrong)
print(right)
# Output:
# [('al', 0.9), ('bea', 0.7), ('cy', 0.9), ('kim', 0.7)]
# [('al', 0.9), ('cy', 0.9), ('bea', 0.7), ('kim', 0.7)]

The last sort decides the main order, and earlier sorts only break its ties. In wrong, the name sort ran last, so the scores are no longer in order.

#Try It

Five problems, easy to hard. Each one uses an idea from this lesson. Work them in order and do not skip a rung. Run the cell at the start to see what the unfinished version prints, then fill in the stubs one at a time.

pythonplayground.py · Pyodide

# RUNG 1 (easy): the lesson's insertion sort, with one thing changed.
# Sort a copy so the LARGEST item comes first. Only one comparison needs to flip.
def insertion_sort_desc(items):
  data = list(items)
  # TODO: for each position i from 1, take data[i] and shift every smaller item
  #       to its left one position right, then drop data[i] into the gap
  return None

# RUNG 2: the merge step on its own, with a tie rule.
# a and b are lists of (name, score), each already sorted by score, smallest first.
# Return one list sorted by score. When two scores tie, the item from a goes first.
def merge_by_score(a, b):
  merged = []
  # TODO: keep a finger i in a and a finger j in b, take the smaller score,
  #       then copy whatever is left of the other list
  return None

# RUNG 3: combine sorting with a dict.
# Return (word, count) pairs, most frequent word first, ties in alphabetical order.
def sort_by_frequency(words):
  counts = {}
  # TODO: count each word in the dict, then sort the pairs with one tuple key
  return None

# RUNG 4: find the bug. This merge sort should keep tied rows in their input order,
# but the output shows ('b', 1) before ('a', 1). Fix ONE character.
def merge_sort_rows(rows):
  if len(rows) <= 1:
      return list(rows)
  middle = len(rows) // 2
  left = merge_sort_rows(rows[:middle])
  right = merge_sort_rows(rows[middle:])
  merged = []
  i = j = 0
  while i < len(left) and j < len(right):
      if left[i][1] < right[j][1]:
          merged.append(left[i])
          i += 1
      else:
          merged.append(right[j])
          j += 1
  merged.extend(left[i:])
  merged.extend(right[j:])
  return merged

# RUNG 5: make it faster, and say the Big-O in a comment.
# scores are whole numbers from 0 to 100, and there can be millions of them.
# sorted(scores) costs O(n log n). Beat it with a counting sort.
def sort_exam_scores(scores):
  # TODO: count how many times each score from 0 to 100 appears, then write them out in order
  return None

print(insertion_sort_desc([4, 9, 1, 7]))          # Expected: [9, 7, 4, 1]
print(merge_by_score([("a", 1), ("c", 3)], [("b", 1), ("d", 2)]))
# Expected: [('a', 1), ('b', 1), ('d', 2), ('c', 3)]
print(sort_by_frequency(["to", "be", "or", "not", "to", "be"]))
# Expected: [('be', 2), ('to', 2), ('not', 1), ('or', 1)]
print(merge_sort_rows([("a", 1), ("b", 1), ("c", 0)]))   # Expected: [('c', 0), ('a', 1), ('b', 1)]
print(sort_exam_scores([90, 72, 100, 72, 0, 55]))        # Expected: [0, 55, 72, 72, 90, 100]

Tests · Five lines print. Rung 1: [9, 7, 4, 1]. Rung 2: [('a', 1), ('b', 1), ('d', 2), ('c', 3)]. Rung 3: [('be', 2), ('to', 2), ('not', 1), ('or', 1)]. Rung 4, after the fix: [('c', 0), ('a', 1), ('b', 1)]. Rung 5: [0, 55, 72, 72, 90, 100].

Hints. Rung 1: the inner while loop keeps shifting while the left item is smaller than the one you hold. Rung 2: use less-than-or-equal so a tie takes from a. Rung 3: a tuple key can negate the count. Rung 4: look at what the merge does when two scores are equal. Rung 5: you need only a list of 101 counters, and the answer is O(n + 101).

#Recap

Sorting makes searching, grouping and ranking cheap. Stable means ties keep their order, and in place means only a small, fixed amount of extra memory. Bubble, selection and insertion sort are O(n²) and in place, and insertion sort costs about n plus the number of inversions, so it is fast on nearly sorted data.

Merge sort halves, sorts and merges, so it is always O(n log n), stable, and uses O(n) extra space. Quick sort partitions around a pivot: O(n log n) on average, O(n²) in the worst case, and a random pivot makes the worst case unlikely. A decision tree shows every comparison sort needs at least log2(n!) comparisons, about n log n. Counting and radix sort skip comparisons and run in O(n + k) and O(d(n + b)).

Python's sorted and list.sort use Timsort: stable, O(n log n) in the worst case, and n - 1 comparisons on sorted input. Use key= to choose the sort value, and a tuple key for ties.

Quick Check1 / 6

Which pair of properties does insertion sort have?

Recap

Key Takeaways

Stable means equal items keep their order, and in place means the sort needs only a small, fixed amount of extra memory
Bubble, selection and insertion sort are O(n²); insertion sort costs about n plus the number of inversions, so it is fast on nearly sorted data
Merge sort is always O(n log n) and stable, with O(n) extra space; quick sort is O(n log n) on average, O(n²) in the worst case, and not stable
A decision tree shows every comparison sort needs at least log2(n!) comparisons, which grows like n log n
Counting sort (O(n + k)) and radix sort (O(d(n + b))) beat n log n by using the values as positions, not by comparing
Python's sorted and list.sort use Timsort: stable, O(n log n) in the worst case, and n - 1 comparisons on sorted input

Sorting Algorithms

Learning Objectives

After this lesson, you will be able to:

Say what stable and in place mean, and tell which sorts have each property
Trace bubble, selection and insertion sort by hand, and explain why insertion sort is fast on nearly sorted data
Write merge sort and quick sort, and explain why the first is always O(n log n) and the second is not
Explain with a decision tree why no comparison sort can beat n log n
Write counting sort and radix sort, and say when they win
Use sorted, list.sort, key= and reverse= correctly, and choose the right sort for a job

Prerequisites

Before You Start

Review

This lesson uses recursion, the idea you met in the recursion lesson: a function that calls itself on a smaller piece of the problem. Merge sort and quick sort both rest on it.

#Why Sort at All

Sorting pays off in four ways.

Searching gets cheap. Binary search needs sorted data.
Equal items end up side by side, so finding duplicates is one pass.
The smallest, the largest, the median and the top few sit at known places.
Two sorted lists can be merged into one in a single pass.

pythonrunnable cell

scores = [72, 91, 65, 88, 91]
ordered = sorted(scores)
print(ordered)
print("lowest:", ordered[0], "highest:", ordered[-1], "median:", ordered[len(ordered) // 2])
print("has a duplicate:", any(a == b for a, b in zip(ordered, ordered[1:])))
# Output:
# [65, 72, 88, 91, 91]
# lowest: 65 highest: 91 median: 88
# has a duplicate: True

One sort answered four questions. The question for the rest of the lesson is what that sort costs, and how to do it cheaply.

#Words You Need Before the Sorts

Three words come up for every sort, so here they are in plain language.

pythonrunnable cell

rows = [("Ana", 3), ("Raj", 1), ("Eli", 3), ("Zed", 1)]
print(sorted(rows, key=lambda row: row[1]))

data = [3, 1, 2]
print(sorted(data), data)      # a new list, the old one is untouched
data.sort()                    # in place: no new list is made
print(data)
# Output:
# [('Raj', 1), ('Zed', 1), ('Ana', 3), ('Eli', 3)]
# [1, 2, 3] [3, 1, 2]
# [1, 2, 3]

#Three Simple Sorts: Bubble, Selection, Insertion

Start with the three methods you could invent in an afternoon. Each one is O(n²) in the typical case, which means doubling the list roughly quadruples the work. Trace each on a tiny list first.

Sweep	Comparisons made	List afterwards
1	5 and 1 swap, 5 and 4 swap, 5 and 2 swap	1, 4, 2, 5
2	1 and 4 stay, 4 and 2 swap	1, 2, 4, 5
3	1 and 2 stay, no swap, so stop	1, 2, 4, 5

Selection sort finds the smallest item in the unsorted part and swaps it to the front of that part. Take 29, 10, 14, 37, 13. The bar marks where the sorted part ends.

Round	Smallest in the rest	List afterwards
1	10	10 \| 29, 14, 37, 13
2	13	10, 13 \| 14, 37, 29
3	14, already in place	10, 13, 14 \| 37, 29
4	29	10, 13, 14, 29, 37

Selection sort always scans everything that is left, so it makes 4 + 3 + 2 + 1 = 10 comparisons here whatever the order. For n items that is n(n-1)/2 comparisons every time.

Insertion sort keeps a sorted part at the front and slides each new item left into its place, like sorting playing cards in your hand. Take 5, 2, 4, 6, 1, 3.

Take	Slides past	List afterwards
2	5	2, 5 \| 4, 6, 1, 3
4	5	2, 4, 5 \| 6, 1, 3
6	nothing	2, 4, 5, 6 \| 1, 3
1	6, 5, 4, 2	1, 2, 4, 5, 6 \| 3
3	6, 5, 4	1, 2, 3, 4, 5, 6

Notice the card 6. It looked at its left neighbour once, found it smaller, and stopped.

What Do You Think?

Insertion sort runs on the list 1, 2, 3, 4, 5, 6, which is already sorted. How many comparisons does it make in total?

Watch the simple sorts raceInteractive

Pick bubble, selection or insertion sort, press play, and compare the counters as the list grows. Then try the others.

Loading visualization...

Now count. The cell sorts the same random lists with all three and reports comparisons, then tries a nearly sorted list and a sorted one.

pythonrunnable cell

import random


def bubble_sort(a):
    """Sort the list in place. Return the number of comparisons."""
    comparisons = 0
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for i in range(end):
            comparisons += 1
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return comparisons


def selection_sort(a):
    """Sort the list in place. Return the number of comparisons."""
    comparisons = 0
    for start in range(len(a) - 1):
        smallest = start
        for i in range(start + 1, len(a)):
            comparisons += 1
            if a[i] < a[smallest]:
                smallest = i
        a[start], a[smallest] = a[smallest], a[start]
    return comparisons


def insertion_sort(a):
    """Sort the list in place. Return the number of comparisons."""
    comparisons = 0
    for i in range(1, len(a)):
        current = a[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if a[j] > current:
                a[j + 1] = a[j]        # shift the bigger item one position right
                j -= 1
            else:
                break
        a[j + 1] = current
    return comparisons


def counts(values):
    return [sort(list(values)) for sort in (bubble_sort, selection_sort, insertion_sort)]


random.seed(7)
for n in (100, 200, 400):
    values = random.sample(range(10 * n), n)
    print(f"n={n}: bubble, selection, insertion = {counts(values)}")

nearly = list(range(400))
nearly[10], nearly[11] = nearly[11], nearly[10]       # one neighbouring pair swapped
print("nearly sorted, n=400:", counts(nearly))
print("already sorted, n=400:", counts(range(400)))
# Output:
# n=100: bubble, selection, insertion = [4674, 4950, 2232]
# n=200: bubble, selection, insertion = [19885, 19900, 10819]
# n=400: bubble, selection, insertion = [79734, 79800, 43937]
# nearly sorted, n=400: [797, 79800, 400]
# already sorted, n=400: [399, 79800, 399]

Each time n doubles, every count grows about four times. That is O(n²). Selection sort is exactly n(n-1)/2, and 400 × 399 / 2 is 79,800.

pythonrunnable cell

people = [("a", 2), ("b", 2), ("c", 1)]
by_swap = list(people)
# selection sort on the score, written with the usual swap
for start in range(len(by_swap) - 1):
    smallest = start
    for i in range(start + 1, len(by_swap)):
        if by_swap[i][1] < by_swap[smallest][1]:
            smallest = i
    by_swap[start], by_swap[smallest] = by_swap[smallest], by_swap[start]
print(by_swap)
print(sorted(people, key=lambda p: p[1]))
# Output:
# [('c', 1), ('b', 2), ('a', 2)]
# [('c', 1), ('a', 2), ('b', 2)]

The swap moved a from the front to the back, behind its twin b. Python's stable sort kept a first.

#Merge Sort: Halve, Sort, Merge

Here is the splitting for eight items, then the merging back.

text

split:   [6 3 8 1 7 2 5 4]
         [6 3 8 1] [7 2 5 4]
         [6 3] [8 1] [7 2] [5 4]
         [6] [3] [8] [1] [7] [2] [5] [4]
merge:   [3 6] [1 8] [2 7] [4 5]
         [1 3 6 8] [2 4 5 7]
         [1 2 3 4 5 6 7 8]

The merge is the clever part. Keep a finger at the front of each sorted half, take the smaller of the two front items, and move that finger. Merge 1, 3, 6, 8 with 2, 4, 5, 7.

Fronts compared	Taken	Output so far
1 and 2	1	1
3 and 2	2	1, 2
3 and 4	3	1, 2, 3
6 and 4	4	1, 2, 3, 4
6 and 5	5	1, 2, 3, 4, 5
6 and 7	6	1, 2, 3, 4, 5, 6
8 and 7	7	1, 2, 3, 4, 5, 6, 7
the left half still has 8	8	1, 2, 3, 4, 5, 6, 7, 8

Eight items took 7 comparisons. Merging two lists of total size m takes at most m - 1 comparisons, so one merge is a single pass.

Merge sort: split the list, then merge the halvesInteractive

Eight numbers split into three levels. Each level is merged back in one pass.

Loading visualization...

pythonrunnable cell

import math
import random


def merge(left, right):
    """Join two sorted lists into one sorted list. Return it and the comparison count."""
    merged = []
    i = j = comparisons = 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:          # <= takes the left item on a tie: this keeps the sort stable
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])              # one side is empty: copy what is left of the other
    merged.extend(right[j:])
    return merged, comparisons


def merge_sort(items):
    """Return a new sorted list and the number of comparisons."""
    if len(items) <= 1:                  # base case: 0 or 1 items are already sorted
        return list(items), 0
    middle = len(items) // 2
    left, left_count = merge_sort(items[:middle])
    right, right_count = merge_sort(items[middle:])
    merged, merge_count = merge(left, right)
    return merged, left_count + right_count + merge_count


print(merge([1, 3, 6, 8], [2, 4, 5, 7]))

random.seed(7)
for n in (100, 200, 400, 800):
    values = [random.random() for _ in range(n)]
    result, count = merge_sort(values)
    bound = math.ceil(n * math.log2(n))
    print(f"n={n}: {count} comparisons, n*log2(n) = {bound}, correct = {result == sorted(values)}")
# Output:
# ([1, 2, 3, 4, 5, 6, 7, 8], 7)
# n=100: 543 comparisons, n*log2(n) = 665, correct = True
# n=200: 1264 comparisons, n*log2(n) = 1529, correct = True
# n=400: 2960 comparisons, n*log2(n) = 3458, correct = True
# n=800: 6712 comparisons, n*log2(n) = 7716, correct = True

Use merge sort when you need a stable O(n log n) guarantee, when sorting linked lists, or when the data is too big for memory and you merge sorted pieces from disk.

#Quick Sort: Partition Around a Pivot

pythonrunnable cell

def partition(a, low, high):
    """Partition a[low..high] around the last item. Return the pivot's final index."""
    pivot = a[high]
    boundary = low                       # a[low:boundary] holds the items smaller than the pivot
    for j in range(low, high):
        if a[j] < pivot:
            a[boundary], a[j] = a[j], a[boundary]
            boundary += 1
        print(f"  j={j}  {a}  boundary={boundary}")
    a[boundary], a[high] = a[high], a[boundary]   # drop the pivot between the two groups
    return boundary


items = [7, 2, 9, 4, 3, 8, 6]
print("start", items, " pivot = 6")
spot = partition(items, 0, len(items) - 1)
print("end  ", items, " pivot sits at index", spot)
# Output:
# start [7, 2, 9, 4, 3, 8, 6]  pivot = 6
#   j=0  [7, 2, 9, 4, 3, 8, 6]  boundary=0
#   j=1  [2, 7, 9, 4, 3, 8, 6]  boundary=1
#   j=2  [2, 7, 9, 4, 3, 8, 6]  boundary=1
#   j=3  [2, 4, 9, 7, 3, 8, 6]  boundary=2
#   j=4  [2, 4, 3, 7, 9, 8, 6]  boundary=3
#   j=5  [2, 4, 3, 7, 9, 8, 6]  boundary=3
# end   [2, 4, 3, 6, 9, 8, 7]  pivot sits at index 3

What Do You Think?

Quick sort always takes the last item as the pivot, and you give it a list of 400 numbers that is already sorted from small to large. About how many comparisons does it make?

Quick sort: pick a pivot, split around itInteractive

Run the random list first. Then switch to the sorted preset and watch one side stay empty.

Loading visualization...

pythonrunnable cell

import random


def quick_sort(a, pivot_rule="last", rng=None):
    """Sort the list in place. Return the number of comparisons."""
    comparisons = 0

    def sort(low, high):
        nonlocal comparisons
        while low < high:
            if pivot_rule == "random":
                pick = rng.randint(low, high)
                a[pick], a[high] = a[high], a[pick]      # move the random pick to the end
            pivot = a[high]
            boundary = low
            for j in range(low, high):
                comparisons += 1
                if a[j] < pivot:
                    a[boundary], a[j] = a[j], a[boundary]
                    boundary += 1
            a[boundary], a[high] = a[high], a[boundary]
            if boundary - low < high - boundary:         # recurse into the smaller side,
                sort(low, boundary - 1)                  # loop on the bigger side
                low = boundary + 1
            else:
                sort(boundary + 1, high)
                high = boundary - 1

    sort(0, len(a) - 1)
    return comparisons


n = 400
random.seed(3)
shuffled = random.sample(range(n), n)
inputs = {"shuffled": shuffled, "already sorted": list(range(n)), "all equal": [5] * n}
for name, data in inputs.items():
    last = quick_sort(list(data))
    rand = quick_sort(list(data), "random", random.Random(1))
    print(f"{name:<15} last-item pivot: {last:>6}   random pivot: {rand:>6}")
print("n*(n-1)/2 =", n * (n - 1) // 2)
# Output:
# shuffled        last-item pivot:   3181   random pivot:   3571
# already sorted  last-item pivot:  79800   random pivot:   3716
# all equal       last-item pivot:  79800   random pivot:  79800
# n*(n-1)/2 = 79800

Three facts fall out of this table.

On shuffled data both rules are near n log n, which is 3,458 for n = 400. That is the average case.
A random pivot has no bad input. No one can build a list that is always slow for it, because the pivot is chosen by chance. A worst case still exists, but it needs terrible luck. Taking the median of the first, middle and last items is another popular rule.
A list of all equal items beats both rules. The test a[j] < pivot is never true, so one side is always empty.

pythonrunnable cell

import random


def quick_sort_3way(items, rng):
    """Return a new sorted list. Three groups: smaller, equal, larger."""
    if len(items) <= 1:
        return list(items)
    pivot = items[rng.randrange(len(items))]
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]       # every copy of the pivot is finished at once
    larger = [x for x in items if x > pivot]
    return quick_sort_3way(smaller, rng) + equal + quick_sort_3way(larger, rng)


rng = random.Random(1)
print(quick_sort_3way([5] * 400, rng) == [5] * 400)        # one pass, then done
data = rng.sample(range(1000), 1000)
print(quick_sort_3way(data, rng) == sorted(data))
# Output:
# True
# True

#Why Comparison Sorts Cannot Beat n log n

Can a cleverer comparison sort do better than n log n? No, and you can see why with a game of yes or no questions.

pythonrunnable cell

import math

print("n      orders (n!)        yes/no questions needed")
for n in (3, 5, 10, 100, 1000):
    orders = math.factorial(n)
    questions = (orders - 1).bit_length()          # the smallest k with 2**k >= n!
    shown = f"{orders:,}" if n <= 10 else f"{len(str(orders))} digits"
    print(f"{n:<6} {shown:<18} {questions}")
# Output:
# n      orders (n!)        yes/no questions needed
# 3      6                  3
# 5      120                7
# 10     3,628,800          22
# 100    158 digits         525
# 1000   2568 digits        8530

The bound is tight. For 800 items it says 6,568 comparisons are unavoidable in the worst case, and our merge sort used 6,712 on a random list. To go faster you must stop using only comparisons.

#Beating n log n: Counting Sort and Radix Sort

The limit holds for sorts that only compare. If the items are whole numbers in a small range, you can use the numbers themselves as positions in a list.

pythonrunnable cell

def counting_sort(values, k):
    """Sort whole numbers in range(k). Time O(n + k), extra space O(k)."""
    counts = [0] * k
    for v in values:
        counts[v] += 1                       # one pass: count each value
    result = []
    for v in range(k):
        result.extend([v] * counts[v])       # one pass over the counts: write each value back
    return result, counts


values = [2, 5, 3, 0, 2, 3, 0, 3]
print(counting_sort(values, 6))
# Output:
# ([0, 0, 2, 2, 3, 3, 3, 5], [2, 0, 2, 3, 0, 1])

pythonrunnable cell

def counting_sort_by(items, digit_of, k):
    """Stable counting sort of items by a small whole-number key in range(k)."""
    counts = [0] * k
    for item in items:
        counts[digit_of(item)] += 1
    start = [0] * k                          # start[d] = where the first item with key d goes
    for d in range(1, k):
        start[d] = start[d - 1] + counts[d - 1]
    result = [None] * len(items)
    for item in items:                       # walk left to right so equal keys keep their order
        d = digit_of(item)
        result[start[d]] = item
        start[d] += 1
    return result


def radix_sort(numbers):
    """Sort non-negative whole numbers, one decimal digit at a time, ones digit first."""
    place = 1
    biggest = max(numbers)
    while place <= biggest:
        numbers = counting_sort_by(numbers, lambda x: (x // place) % 10, 10)
        print(f"after the {place}s digit:", numbers)
        place *= 10
    return numbers


radix_sort([170, 45, 75, 90, 802, 24, 2, 66])
# Output:
# after the 1s digit: [170, 90, 802, 2, 24, 45, 75, 66]
# after the 10s digit: [802, 2, 24, 45, 66, 170, 75, 90]
# after the 100s digit: [2, 24, 45, 66, 75, 90, 170, 802]

#Python's sorted and Timsort

pythonrunnable cell

import random


class Counted:
    """A number that counts every time it is compared with <."""
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.comparisons += 1
        return self.value < other.value


def comparisons_to_sort(values):
    Counted.comparisons = 0
    sorted(Counted(v) for v in values)
    return Counted.comparisons


random.seed(1)
shuffled = random.sample(range(1000), 1000)
print("already sorted:", comparisons_to_sort(sorted(shuffled)))
print("reversed:      ", comparisons_to_sort(sorted(shuffled, reverse=True)))
print("shuffled is more:", comparisons_to_sort(shuffled) > 5000)
# Output:
# already sorted: 999
# reversed:       999
# shuffled is more: True

What Do You Think?

What does this print? rows = [("ada", 3), ("bo", 1), ("cy", 3)] print(sorted(rows, key=lambda r: r[1], reverse=True))

A few keys cover most needs.

pythonrunnable cell

from operator import itemgetter

rows = [("ada", 0.91), ("bo", 0.85), ("cy", 0.91), ("di", 0.85), ("ed", 0.97)]
print(sorted(rows, key=itemgetter(1), reverse=True))                 # ties keep their input order
print(sorted(rows, key=lambda r: (-r[1], r[0])))                     # score high to low, then name

words = ["Zebra", "apple", "Mango", "banana"]
print(sorted(words))                                                 # capitals sort before lowercase
print(sorted(words, key=str.lower))
print(sorted(words, key=len))                                        # ties keep their input order

ranked = sorted(rows, key=lambda r: r[0])                            # sort by the tie-break first
ranked = sorted(ranked, key=lambda r: r[1], reverse=True)            # then by the main key
print(ranked == sorted(rows, key=lambda r: (-r[1], r[0])))
# Output:
# [('ed', 0.97), ('ada', 0.91), ('cy', 0.91), ('bo', 0.85), ('di', 0.85)]
# [('ed', 0.97), ('ada', 0.91), ('cy', 0.91), ('bo', 0.85), ('di', 0.85)]
# ['Mango', 'Zebra', 'apple', 'banana']
# ['apple', 'banana', 'Mango', 'Zebra']
# ['Zebra', 'apple', 'Mango', 'banana']
# True

#Heap Sort in One Paragraph

The array version works inside the list and needs O(1) extra space. It is not stable, and it jumps around in memory, which is why quick sort is usually faster in practice.

pythonrunnable cell

import heapq


def heap_sort(items):
    """Build a heap in O(n), then pop the smallest item n times at O(log n) each."""
    heap = list(items)
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]


print(heap_sort([5, 2, 9, 1, 7, 3]))
# Output:
# [1, 2, 3, 5, 7, 9]

#Choosing a Sort

Here is every sort in one table. "Extra space" counts memory beyond the list itself.

Sort	Best	Average	Worst	Extra space	Stable
Bubble	O(n)	O(n²)	O(n²)	O(1)	yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	no
Insertion	O(n)	O(n²)	O(n²)	O(1)	yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	yes
Quick, random pivot	O(n log n)	O(n log n)	O(n²)	O(log n)	no
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	no
Counting	O(n + k)	O(n + k)	O(n + k)	O(n + k)	yes, when written stably
Radix	O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	yes
Timsort	O(n)	O(n log n)	O(n log n)	O(n)	yes

Here is how to choose.

Default to sorted or list.sort. It is stable, handles partly sorted data well, and runs in C.
Need only the smallest or largest? Use min or max, one pass of n - 1 comparisons. Sorting a list to read its first item does far more work.
Need only the k best? A heap of size k beats a full sort when k is small.
Keys are small whole numbers? Counting sort is O(n + k), and radix sort handles fixed-width keys.
Will you search the data many times? Sort once, then use bisect for each lookup.
Writing your own because memory is tight or the interviewer asks? Quick sort with a random pivot works in place. Heap sort works in place with a firm O(n log n) bound. Merge sort is the stable choice.

#How Sorting Shows Up in ML

pythonrunnable cell

scores = [0.12, 0.88, 0.45, 0.91, 0.30, 0.77]

order = sorted(range(len(scores)), key=lambda i: scores[i], reverse=True)   # a pure Python "argsort"
print(order)
print("top 3 documents:", order[:3], [scores[i] for i in order[:3]])
# Output:
# [3, 1, 5, 2, 4, 0]
# top 3 documents: [3, 1, 5] [0.91, 0.88, 0.77]

Sorting the positions, not the scores, tells you which documents won, and that is what argsort returns.

#Common Mistakes

Watch Out

Using the result of list.sort()

Fix: Call scores.sort() on its own line, or write ranked = sorted(scores) to get a new list.

pythonrunnable cell

scores = [0.62, 0.91, 0.55]
ranked = scores.sort(reverse=True)
print(ranked, scores)
# Output:
# None [0.91, 0.62, 0.55]

list.sort() changes the list and returns None, as a signal that nothing new was made. Code such as scores.sort()[:3] then fails with a TypeError, and ranked holds nothing.

Watch Out

Sorting data that holds None

Fix: Say where missing values go, inside the key function, or remove them first.

pythonrunnable cell

scores = [0.9, None, 0.4, 0.7]
try:
    sorted(scores)
except TypeError as error:
    print(error)

print(sorted(scores, key=lambda s: float("-inf") if s is None else s))
# Output:
# '<' not supported between instances of 'NoneType' and 'float'
# [None, 0.4, 0.7, 0.9]

Sorting only needs the less-than test, and Python refuses to compare None with a number. Missing values are common in real data, so give the key a rule.

Watch Out

Sorting by two keys in the wrong order

Fix: With two stable sorts, sort by the tie-break first and by the main key last. Or use one sort with a tuple key.

pythonrunnable cell

rows = [("kim", 0.7), ("al", 0.9), ("bea", 0.7), ("cy", 0.9)]
wrong = sorted(sorted(rows, key=lambda r: r[1], reverse=True), key=lambda r: r[0])
right = sorted(sorted(rows, key=lambda r: r[0]), key=lambda r: r[1], reverse=True)
print(wrong)
print(right)
# Output:
# [('al', 0.9), ('bea', 0.7), ('cy', 0.9), ('kim', 0.7)]
# [('al', 0.9), ('cy', 0.9), ('bea', 0.7), ('kim', 0.7)]

The last sort decides the main order, and earlier sorts only break its ties. In wrong, the name sort ran last, so the scores are no longer in order.

#Try It

pythonplayground.py · Pyodide

#Recap

Python's sorted and list.sort use Timsort: stable, O(n log n) in the worst case, and n - 1 comparisons on sorted input. Use key= to choose the sort value, and a tuple key for ties.

Quick Check1 / 6

Which pair of properties does insertion sort have?

Recap

Key Takeaways

Stable means equal items keep their order, and in place means the sort needs only a small, fixed amount of extra memory
Bubble, selection and insertion sort are O(n²); insertion sort costs about n plus the number of inversions, so it is fast on nearly sorted data
Merge sort is always O(n log n) and stable, with O(n) extra space; quick sort is O(n log n) on average, O(n²) in the worst case, and not stable
A decision tree shows every comparison sort needs at least log2(n!) comparisons, which grows like n log n
Counting sort (O(n + k)) and radix sort (O(d(n + b))) beat n log n by using the values as positions, not by comparing
Python's sorted and list.sort use Timsort: stable, O(n log n) in the worst case, and n - 1 comparisons on sorted input

Sorting Algorithms

#Why Sort at All

#Words You Need Before the Sorts

#Three Simple Sorts: Bubble, Selection, Insertion

#Merge Sort: Halve, Sort, Merge

#Quick Sort: Partition Around a Pivot

#Why Comparison Sorts Cannot Beat n log n

#Beating n log n: Counting Sort and Radix Sort

#Python's sorted and Timsort

#Heap Sort in One Paragraph

#Choosing a Sort

#How Sorting Shows Up in ML

#Common Mistakes

#Try It

#Recap

Your Reflection

Continue Learning

Discussion

Sorting Algorithms

#Why Sort at All

#Words You Need Before the Sorts

#Three Simple Sorts: Bubble, Selection, Insertion

#Merge Sort: Halve, Sort, Merge

#Quick Sort: Partition Around a Pivot

#Why Comparison Sorts Cannot Beat n log n

#Beating n log n: Counting Sort and Radix Sort

#Python's sorted and Timsort

#Heap Sort in One Paragraph

#Choosing a Sort

#How Sorting Shows Up in ML

#Common Mistakes

#Try It

#Recap

Your Reflection

Continue Learning

Discussion