Sorting Basics: Stability, In-Place, Comparison Sorts

Before comparing bubble, merge or quick sort, learn the words every sorting algorithm is judged by. Time is only one. Extra memory and stability decide which algorithm is even allowed, and the comparison lower bound explains why the fast general-purpose sorts all land on O(n log n). Each term below is defined, run in Python, and checked by brute force.

The problem it solves

"Sort this" hides several questions:

• How long? The number of comparisons and moves, as the input grows.
• How much extra memory? Some sorts rearrange the array where it lies; others need a second array as large as the first.
• What happens to ties? When two records have equal keys, does their original order survive?
• What does it know about the keys? Comparing pairs is the general case; knowing they are small integers opens other doors.

The vocabulary turns "which sort?" into a short checklist, the one the which-sort-when guide builds on.

The intuition

• Comparison sort. It learns about the data only by asking "is a before b?". Bubble, insertion, selection, merge, quick and heap sort are all comparison sorts.
• Stable. Records with equal keys come out in the order they went in. Insertion and merge sort are stable as usually written; selection, quick and heap sort usually are not, because a long-distance swap can jump one tied record over another.
• In place. The algorithm uses only a small, fixed amount of memory beyond the input, usually defined as O(1) and sometimes loosened to O(log n) for quick sort's recursion stack. Merge sort's ordinary version needs O(n) extra.
• Adaptive. It runs faster on input that is already nearly sorted. Insertion sort is the textbook case.

Stability is the one people discover the hard way. It is what makes layered sorting work: sort by the secondary key first, then stably by the primary key, and ties in the primary key stay ordered by the secondary one.

And the bound: a comparison sort must distinguish all n! possible orderings of its input, and each yes-or-no comparison at best halves the possibilities still in play. So some input needs at least log₂(n!) comparisons, which grows like n log n. No cleverness inside the comparison model beats that; only sorts that look at the keys themselves, like counting and radix sort, can.

Watch it run

The animation lays out five records in the order they arrived: Ada from Rome, Bo from Lima, Cy from Rome, Di from Lima and Ed from Oslo, and states the three criteria, time, extra memory and stability. Then it sorts by city. Two records share Lima and two share Rome, so two ties have to be broken. A stable sort breaks ties by leaving them alone: the result is Bo, Di, Ed, Ada, Cy, and Bo still precedes Di, Ada still precedes Cy. An unstable sort is free to flip them, giving Di, Bo, Ed, Cy, Ada: the same cities and the same set, but the arrival order inside each city is gone. The last frame says why it matters: sort by name, then by city, and only a stable sort keeps the first sort's work intact.

The code

The animation's records through Python's built-in sort, which is stable. Then a selection sort, which is in place and makes at most n - 1 swaps, but is not stable: its single swap carries write past its tie with test:

people = [("Ada", "Rome"), ("Bo", "Lima"), ("Cy", "Rome"), ("Di", "Lima"), ("Ed", "Oslo")]
by_city = sorted(people, key=lambda p: p[1])          # stable
print([name for name, _ in by_city])                  # ['Bo', 'Di', 'Ed', 'Ada', 'Cy']

def selection_sort(a, key=lambda x: x):
    """In place, at most n - 1 swaps, and NOT stable: a swap can jump a tie."""
    a = list(a)
    swaps = 0
    for i in range(len(a)):
        m = min(range(i, len(a)), key=lambda j: key(a[j]))
        if m != i:
            a[i], a[m] = a[m], a[i]
            swaps += 1
    return a, swaps

tasks = [("write", 2), ("test", 2), ("plan", 1)]
out, swaps = selection_sort(tasks, key=lambda t: t[1])
print(out, swaps)       # [('plan', 1), ('test', 2), ('write', 2)] 1
print(sorted(tasks, key=lambda t: t[1]))   # [('plan', 1), ('write', 2), ('test', 2)]

(The function copies its input only so the examples can reuse tasks.) Any sort can be made stable by decorating each record with its original position, so no two keys are ever equal. And a two-pass layered sort gives the same result as one sort on a tuple key:

decorated, _ = selection_sort([(t[1], i, t) for i, t in enumerate(tasks)])
print([t for _, _, t in decorated])        # [('plan', 1), ('write', 2), ('test', 2)]

two_pass = sorted(sorted(people), key=lambda p: p[1])   # by name, then by city
print(two_pass == sorted(people, key=lambda p: (p[1], p[0])))   # True

The lower bound, checked rather than quoted. A merge sort counts its comparisons on every one of the n! permutations of n distinct items; its worst case never dips below ⌈log₂(n!)⌉, and it is far below the n(n - 1)/2 that insertion or bubble sort can need:

import math
from itertools import permutations

def merge_sort(a, count):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid], count), merge_sort(a[mid:], count)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        count[0] += 1
        if right[j] < left[i]:          # strict: ties take the left item, so stable
            out.append(right[j]); j += 1
        else:
            out.append(left[i]); i += 1
    return out + left[i:] + right[j:]

for n in range(2, 9):
    bound = math.ceil(math.log2(math.factorial(n)))
    worst = 0
    for p in permutations(range(n)):
        c = [0]
        assert merge_sort(list(p), c) == list(range(n))
        worst = max(worst, c[0])
    print(n, bound, worst, n * (n - 1) // 2, round(n * math.log2(n), 1))
# 2 1 1 1 2.0
# 3 3 3 3 4.8
# 4 5 5 6 8.0
# 5 7 8 10 11.6
# 6 10 11 15 15.5
# 7 13 14 21 19.7
# 8 16 17 28 24.0

Finally, 1,500 seeded record lists full of ties: decorated selection sort equals Python's stable sort, tied records keep input order, two passes equal the tuple key, and selection sort stays within n - 1 swaps:

import random
ok = True
for seed in range(1_500):
    r = random.Random(seed)
    recs = [(r.choice("abc"), r.randint(0, 3), i) for i in range(r.randint(0, 7))]
    stable = sorted(recs, key=lambda x: x[1])
    sel, _ = selection_sort([(x[1], i, x) for i, x in enumerate(recs)])
    ok &= [x for _, _, x in sel] == stable
    ok &= [x[2] for x in stable] == sorted(range(len(recs)), key=lambda i: (recs[i][1], i))
    ok &= sorted(sorted(recs, key=lambda x: x[0]), key=lambda x: x[1]) == sorted(recs, key=lambda x: (x[1], x[0]))
    plain, swaps = selection_sort([x[1] for x in recs])
    ok &= plain == sorted(x[1] for x in recs) and swaps <= max(len(recs) - 1, 0)
print(ok)                                  # True

The complexity

• Comparison sorts: at least ⌈log₂(n!)⌉ comparisons in the worst case, which is Θ(n log n). Merge and heap sort stay within O(n log n) in the worst case; quick sort only on average.
• Simple sorts: insertion, selection and bubble sort take O(n²) comparisons in the worst case; insertion sort drops to O(n) on sorted input.
• Memory: selection, insertion and heap sort are in place; array merge sort needs O(n) extra.

The Big-O cheat sheet has the full sorting table, including a stable column.

Where it goes wrong

• Layering with an unstable sort, or in the wrong order. The earlier pass is silently scrambled. For "by city, then by name", sort by name first, stably, or use one tuple key.
• "In place" in the API sense. list.sort() mutates the list and returns None, but Timsort's merges can still use temporary memory, up to about half the list (from memory). The Python cheat sheet covers the a = a.sort() bug.
• Expecting to beat n log n by comparing. Only non-comparison sorts such as counting and radix sort can, and only on suitable keys.

As of October 2026, Python's sorted and list.sort are guaranteed stable; CPython's implementation is Timsort, with a merge policy updated to Powersort in version 3.11 (from memory).

When it shows up in interviews

As direct questions, "what does stable mean?", "is quick sort stable?", "what is the comparison lower bound?", and inside design questions such as sorting a table by several columns. It also decides follow-ups to selection sort and merge vs quick sort: which one would you pick if ties must keep their order, or if memory is tight?

How to say it in an interview

"I judge a sort on time, extra memory and stability. A stable sort keeps equal keys in input order, which is what makes multi-key sorting by successive passes work; merge and insertion sort are stable, quick, heap and selection sort usually aren't, and any sort can be made stable by adding the original index to the key. In-place means O(1) extra memory, sometimes loosened to O(log n) for quick sort's stack. Any comparison sort needs at least log₂(n!) comparisons, which is Θ(n log n), so to go faster you need to exploit the keys, as counting or radix sort does."

The next lesson starts the tour: bubble sort.