Elementary Sorts and What They Teach

1Why study sorts nobody uses

Not for the algorithms. For the habit of naming what stays true while everything else changes.

You will never write bubble sort in production. Python's sorted() is faster than anything you would write, and it is one word.

Elementary sorts are worth an hour anyway, for three reasons:

1. They are the smallest complete examples of a loop invariant — the single most useful tool for reasoning about a loop you did not write.
2. Insertion sort is genuinely used, inside every industrial sort, for small or nearly-sorted chunks.
3. Stability is defined here, and it changes answers in real programs.

2Selection sort

The most human algorithm: find the smallest, put it first, repeat. Predictable to a fault.

def selection_sort(xs):
    n = len(xs)
    for i in range(n - 1):
        # INVARIANT: xs[0:i] holds the i smallest values, in final order.
        smallest = i
        for j in range(i + 1, n):
            if xs[j] < xs[smallest]:
                smallest = j
        xs[i], xs[smallest] = xs[smallest], xs[i]
        # The invariant now holds for i+1.
    return xs

Two things make selection sort distinctive:

• It does the same work on every input. Already sorted? Same number of comparisons. That is unusual, and occasionally useful when you need predictable timing.
• It performs at most n−1 swaps — the minimum possible for any sort that moves elements. If a write is far more expensive than a read (flash memory, say, which wears out), that is a real argument.

3Bubble sort

Repeatedly swap out-of-order neighbours. Famous, slow, and the clearest picture of what sorting does.

Walk the array comparing adjacent pairs and swapping when they are out of order. One pass moves the largest remaining value all the way to the end — it “bubbles up”. Repeat until a pass makes no swaps.

def bubble_sort(xs):
    n = len(xs)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            # INVARIANT: xs[n-i:] holds the i largest values, in final order.
            if xs[j] > xs[j + 1]:
                xs[j], xs[j + 1] = xs[j + 1], xs[j]
                swapped = True
        if not swapped:        # a whole pass with no swaps → already sorted
            break
    return xs

The swapped flag is what makes bubble sort adaptive: on already-sorted input, one pass finds nothing to swap and it exits in O(n). Without that flag it is O(n²) on every input, which is how it is usually written and why it has such a poor reputation.

Bubble sort is stable because it only ever swaps adjacent elements, and only when they are strictly out of order. Equal neighbours are left alone, so equal elements can never cross.

4Insertion sort

The one you actually use. It is how everybody sorts cards, and it is inside every industrial sort you have ever run.

def insertion_sort(xs):
    for i in range(1, len(xs)):
        # INVARIANT: xs[0:i] is sorted (among itself, not finally placed).
        key = xs[i]
        j = i - 1
        while j >= 0 and xs[j] > key:    # note: > not >=, which keeps it stable
            xs[j + 1] = xs[j]            # shift right
            j -= 1
        xs[j + 1] = key                  # drop into the gap
    return xs

Note the difference in invariant. Selection sort's prefix holds values that are finally placed. Insertion sort's prefix is sorted among itself but every element in it may still move right when a smaller value arrives. Both are correct; they are different promises.

Why real sorts use it

Python's sorted() is Timsort. Java's Arrays.sort is a dual-pivot quicksort. Both switch to insertion sort for runs below about 32–64 elements. Two reasons:

• Tiny constant factor. No recursion, no allocation, no partitioning — just a tight loop over contiguous memory that the CPU cache loves.
• Adaptivity. Real data arrives partly ordered far more often than randomly. On nearly-sorted input the inner while exits immediately and the whole thing is O(n).

5Stability, and why it changes answers

A property that sounds like trivia until the first time it silently corrupts a report.

A sort is stable if elements that compare equal keep their original relative order. Unstable sorts may reorder them arbitrarily.

It matters the moment you sort by one field having already sorted by another:

people = [
    ("Ada",   "Engineering"),
    ("Grace", "Engineering"),
    ("Alan",  "Research"),
    ("Kay",   "Engineering"),
]

# Goal: grouped by department, alphabetical within each department.
# With a STABLE sort you can do it in two passes:

people.sort(key=lambda p: p[0])      # 1. by name
people.sort(key=lambda p: p[1])      # 2. by department

# → Ada, Grace, Kay (Engineering), then Alan (Research)
#
# The second sort did NOT disturb the name order established by the first,
# because within a department every element compares equal. That is
# stability doing real work.
#
# With an unstable sort the name order would be scrambled and you would
# have to sort by a compound key instead:
people.sort(key=lambda p: (p[1], p[0]))

6Sorting in Python

What you will actually call, and the three arguments worth knowing.

sorted(xs) returns a new list; xs.sort() sorts in place and returns None. Both use Timsort: a merge sort that detects existing sorted runs and merges them, falling back to insertion sort on short runs. It is stable, and it is O(n) on already-sorted input.

xs = [3, 1, 2]

sorted(xs)                  # → [1, 2, 3];  xs is unchanged
xs.sort()                   # → None;       xs is now sorted
                            # `xs = xs.sort()` sets xs to None. Classic.

# key: a function computing what to sort BY
words = ["banana", "kiwi", "apple"]
sorted(words, key=len)                      # by length
sorted(words, key=str.lower)                # case-insensitive
sorted(people, key=lambda p: p.age)         # by an attribute

# reverse
sorted(xs, reverse=True)

# Multi-field: a tuple key sorts by the first, then the second, ...
sorted(people, key=lambda p: (p.dept, p.name))

# Mixed directions — negate a numeric field:
sorted(people, key=lambda p: (p.dept, -p.age))

# For a non-numeric field you cannot negate, use stability instead:
people.sort(key=lambda p: p.name)                  # ascending name
people.sort(key=lambda p: p.dept, reverse=True)    # descending dept, names intact

The comparison that matters

>_Playground

Race the three sorts, count their operations, and see adaptivity and stability for yourself.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.