Sorting: Why Some Sorts Are Slow

13.1Why study slow sorts?

You will never ship bubble sort. You study it because it is the clearest example in all of computing of a genuine trade: two methods, both obviously correct, separated by a complexity class you can feel on a laptop within thirty seconds.

Sorting also underpins week 12 (binary search needs sorted data), week 9 (the sort-and- compare anagram solution) and any report you will ever produce from data.

13.2Bubble sort

Walk along the row comparing neighbours; swap them if they are out of order. Each full pass drags the largest remaining value to the end — it "bubbles up". Repeat until a pass makes no swaps.

def bubble_sort(data):
    """Sorts a copy of data. Returns (sorted list, comparisons, swaps)."""
    items = data[:]                      # work on a copy
    comparisons = swaps = 0
    n = len(items)

    for end in range(n - 1, 0, -1):      # shrinking unsorted region
        swapped = False
        for i in range(end):
            comparisons += 1
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swaps += 1
                swapped = True
        if not swapped:                  # already sorted — stop early
            break

    return items, comparisons, swaps

print(bubble_sort([5, 1, 4, 2, 8]))

Cost. Passes shrink: (n−1) + (n−2) + … + 1 = n(n−1)/2 comparisons — O(n²). The early exit gives a best case of O(n) on data that is already sorted, which is bubble sort's only redeeming feature. (Here the early exit fires after the third pass finds nothing to swap, so it stops at 9 comparisons instead of the full 10.)

13.3Selection sort

Find the smallest item, put it first. Find the smallest of the rest, put it second. Continue. This is what most people do with a hand of cards.

def selection_sort(data):
    items = data[:]
    comparisons = swaps = 0

    for start in range(len(items)):
        smallest = start
        for i in range(start + 1, len(items)):
            comparisons += 1
            if items[i] < items[smallest]:
                smallest = i
        if smallest != start:
            items[start], items[smallest] = items[smallest], items[start]
            swaps += 1

    return items, comparisons, swaps

Same n(n−1)/2 comparisons — O(n²) in every case, best included, because it cannot know it is finished early. But it performs at most n−1 swaps, against bubble sort's possible n²/2. If moving items is expensive and comparing them is cheap, that matters. Two algorithms in the same class can still differ in ways worth measuring.

13.4Insertion sort, and all three by hand

The third classic completes the set. Take each item and slide it back into its correct place among the already-sorted items on its left — the way most people order a hand of playing cards as they pick them up.

def insertion_sort(data):
    items = data[:]
    comparisons = shifts = 0

    for i in range(1, len(items)):
        current = items[i]               # the card in your hand
        j = i - 1
        while j >= 0:
            comparisons += 1
            if items[j] > current:       # make room by shifting right
                items[j + 1] = items[j]
                shifts += 1
                j -= 1
            else:
                break
        items[j + 1] = current           # drop it into the gap

    return items, comparisons, shifts

print(insertion_sort([5, 1, 4, 2, 8]))

Insertion sort is O(n²) in the worst case, but genuinely fast on nearly-sorted data — on an already-sorted list every item drops straight in after a single comparison, giving O(n). That is why real sorting libraries use it for small chunks.

Now the point of this section: sort [5, 1, 4, 2, 8] by hand with each method, writing the list after every pass, and confirm your counts against the three outputs above.

Three correct answers, three different amounts of work on the very same five numbers. Selection sort always does its full 10 comparisons; bubble sort's early exit saves it one; insertion sort does the fewest here because the data was not badly scrambled. The class is the same for all three — the constants are not.

13.5Where n log n comes from

All three sorts above compare, in the worst case, every item with essentially every other. The better sorts refuse to do that, using a divide-and-conquer idea:

1. Split the list into two halves.
2. Sort each half (by the same method, on smaller pieces).
3. Merge the two sorted halves by repeatedly taking the smaller front item — one pass, O(n).

How many times can you split a list of n items in half? log n times — the same halving from weeks 1 and 12. Each of those levels does O(n) work merging. So the total is n × log n.

You will not implement merge sort in this course — writing it well needs recursion, which belongs to the follow-on course. What you need is the intuition ("split, sort, merge — log n levels of n work each") and the ability to recognise its 2.1–2.2 ratio in a doubling experiment.

13.6Python's sorted(), and how far ahead it is

import time, random

for n in [1000, 2000, 4000, 8000]:
    data = [random.randrange(1000000) for _ in range(n)]

    start = time.perf_counter()
    result_b, comps, swaps = bubble_sort(data)
    t_bubble = time.perf_counter() - start

    start = time.perf_counter()
    result_p = sorted(data)
    t_python = time.perf_counter() - start

    print(f"n={n:>5}  bubble {t_bubble:8.4f}s ({comps:,} comparisons)"
          f"   sorted() {t_python:.5f}s   {t_bubble/t_python:,.0f}x")
    assert result_b == result_p          # both are correct!

The assert line matters: both produce identical output. The difference is entirely in how the answer is reached. Read the two time columns down the page as a doubling experiment, exactly as in weeks 5–7:

A ratio column that sits at 4 is the fingerprint of O(n²); one that sits just above 2 is the fingerprint of O(n log n). You do not need to know the constant, the machine or the language to read the class straight off those numbers — which is the whole method of this course. And the final speedup column keeps growing precisely because the two lines belong to different classes: at n = 100 000 bubble sort would need roughly 5 000 million comparisons and about fifteen minutes; sorted() takes about a twentieth of a second.

13.7Using sorting properly

data = [5, 2, 9, 1]

new = sorted(data)              # returns a new list, leaves data alone
data.sort()                     # sorts in place, returns None

names = ["Cem", "ada", "Bilal"]
print(sorted(names))                          # capitals first — probably not what you want
print(sorted(names, key=str.lower))           # case-insensitive

students = [("Ada", 88), ("Bilal", 72), ("Cem", 91)]
print(sorted(students, key=lambda s: s[1], reverse=True))   # by grade, best first

One more cost worth knowing: sorting inside a loop is a classic accidental disaster. Sorting a list of n items m times is O(m · n log n) when sorting once outside the loop would have done. Ask yourself every time: does this need to happen again?

13.8Stability, and sorting by more than one key

A sort is stable when items that compare equal keep their original order. Python's sorted and list.sort are stable — a guarantee, not an accident — and it is more useful than it first sounds.

scores = [("Ada", 88), ("Bilal", 88), ("Cem", 72)]

print(sorted(scores, key=lambda p: p[1], reverse=True))

Ada and Bilal both scored 88, and Ada stays ahead of Bilal because she came first in the input. An unstable sort would be free to swap them, and you would have no way to predict the order of ties.

Stability is what lets you sort by several keys in stages: sort by the least important key first, then by the most important, and the earlier order survives inside each group. Or, more directly, hand key a tuple and let Python compare left to right:

students = [
    ("maths",   "Bilal"),
    ("art",     "Cem"),
    ("maths",   "Ada"),
    ("art",     "Ada"),
]

# by subject A→Z, then by name A→Z within each subject
print(sorted(students, key=lambda s: (s[0], s[1])))

The tuple (subject, name) is compared position by position: subjects first, and names only to break a tie on subject. To mix directions — say subject ascending but grade descending — sort in two stable passes (grade first with reverse=True, then subject), because a single tuple key cannot reverse just one of its parts.

13.9Try it yourself

13.10Self-check

13.11Homework

13.12Words from this week

13.13Chapter problem set — Skiena 2.10

Sorting rested on a summation — adding up n(n−1)/2 comparisons — so this is a good week to practise reading a pattern and pinning down the expression behind it. Here is one of Skiena's, solved the way this course likes: spot the pattern, then say why.

def next_row(row):
    padded = [0, 0] + row + [0, 0]        # room for the row widening by one each side
    return [padded[i] + padded[i + 1] + padded[i + 2] for i in range(len(row) + 2)]

row = [1]
for i in range(1, 6):
    print(f"row {i}: sum {sum(row):>3}   {row}")
    row = next_row(row)