Elementary Sorts & Stability
Bubble sort, selection sort and insertion sort are the algorithms everyone learns first and almost nobody calls directly. They still earn a full lesson. They are the smallest algorithms on which to practise writing a loop invariant, proving it, and counting operations exactly. They introduce the two properties that decide which sort a library ships — stability and adaptivity — and the quantity that connects them, the number of inversions. And insertion sort is not a museum piece: it runs inside Timsort, introsort and pdqsort, so it runs every time you call list.sort() in Python, Arrays.sort on objects in Java, std::sort in C++ or Array.prototype.sort in a browser.
By the end you will be able to prove all three correct, state their exact comparison and swap counts, prove that insertion sort shifts exactly once per inversion, explain stability with a trace, and say why Shell sort's complexity is still partly open.
Why this exists
Sorting is older than computers: the punched-card machines that grew out of the 1890 US census included card sorters that sorted one digit per pass, and clerks filing index cards used insertion. Sorting was among the first problems programmed on stored-program computers, and the quadratic methods — by exchange, selection and insertion — were catalogued by the mid-1950s. Knuth's The Art of Computer Programming, Volume 3, devotes most of §5.2 to them; the analysis on this page is largely his.
Each elementary sort is good at something. Insertion sort runs in , where is the number of out-of-order pairs, so it is the fastest simple sort on tiny arrays and on nearly sorted ones. Selection sort performs at most swaps, which matters when writes cost far more than reads. Bubble sort is mostly a teaching tool, though its structure is what a parallel odd-even transposition sort runs on a line of processors.
The concepts they introduce do not go away either. Stability decides whether you can sort a table by "last name, then first name" in two passes and is the reason radix sort works. Inversions measure how far an array is from sorted; you will count them with merge sort in the next lesson and meet them again in ranking metrics such as Kendall's tau. Adaptivity is the design principle behind Timsort.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "Minimum number of adjacent swaps to sort" | The number of inversions (bubble/insertion sort perform exactly ); count it in with merge sort |
| "The array is almost sorted", "each element is at most away from its final position" | Insertion sort: because ; or a size- heap for |
| Elements arrive one at a time and you must keep them sorted | Insertion into a sorted prefix (online insertion sort) — fine for small ; use a balanced tree or heap when is large |
| "Sort by X, and for equal X keep the original order" / "then by Y" | A stable sort; or sort by Y first, then stable-sort by X |
| Writes are expensive (flash, EEPROM, huge records) / "minimise swaps" | Selection sort ( swaps) or cycle sort (minimum writes) |
| a few dozen inside a bigger algorithm | Insertion sort as the base case of a recursive sort |
| "Only allowed to reverse a prefix", "only swap with the front", restricted moves | Selection-sort skeleton: put the maximum in place, shrink the problem (pancake sorting) |
| Sorting a linked list with no random access | Insertion sort (, simple) or merge sort (, next lesson) |
| up to or more, arbitrary order | Not an elementary sort: shifts. Use the built-in sort |
Intuition & first principles
What it means to be unsorted
An array is sorted (non-decreasing) when for every . To measure how far it is from sorted, count the pairs that are in the wrong order.
Definition. An inversion is a pair of indices with and . Write for the number of inversions.
For [5, 2, 4, 6, 1, 3] the inversions are the pairs of values , so . Three facts about inversions carry most of this page:
- if and only if is sorted. If no pair is out of order, in particular no adjacent pair is; conversely if every adjacent pair is in order, transitivity puts every pair in order.
- , with the maximum reached exactly when the array is strictly decreasing.
- Swapping an adjacent inverted pair removes exactly one inversion. If and you swap them, the pair stops being an inversion. Every other pair keeps its relative order: an element outside positions sees both of them on the same side before and after the swap.
Fact 3 is the key. Any algorithm that sorts using only adjacent swaps must perform at least swaps, and an algorithm that only ever swaps adjacent inverted pairs performs exactly . Bubble sort and insertion sort are both algorithms of the second kind.
Average inversions. Over all orderings of distinct values, the average number of inversions is exactly . Pair every permutation with its reverse. For any pair of positions, the two values are inverted in exactly one of the two permutations, so each such pair of permutations has inversions between them, and the average is half of that. For that is 249,750 — a random array is "half as unsorted" as a reversed one, and any adjacent-swap sort must do about swaps on it.
Three strategies
Each elementary sort takes one local view of the problem.
- Bubble sort — fix what you see. Walk the array, swapping every adjacent pair that is out of order. After one full pass the largest element has been carried ("bubbled") to the end. Repeat on the remaining prefix. Stop early if a pass makes no swaps.
- Selection sort — choose the right element for each position. For position 0, find the minimum of the whole array and swap it in. For position 1, find the minimum of the rest. And so on.
- Insertion sort — keep a sorted prefix and grow it. Treat
a[0..i-1]as a sorted hand of cards. Take the next carda[i], slide larger cards one place to the right until you find where it belongs, and drop it into the gap.
The precise version of the card analogy is the invariant: before iteration , a[0..i-1] contains the original first elements, in sorted order.
Selection and insertion are duals. Selection sort works hard to choose the next element (a scan over the unsorted part) and places it trivially (one swap). Insertion sort takes the next element for free and works hard to place it (a scan over the sorted part). That is why insertion sort can stop early and selection sort cannot: the scan over the sorted part stops at the first element that is not larger, but a scan for a minimum must look at everything.
Mechanics
Bubble sort with early exit
flowchart TD
S["i = 0"] --> P{"i < n - 1 ?"}
P -->|"no"| D["done"]
P -->|"yes"| R["swapped = false, j = 0"]
R --> J{"j < n - 1 - i ?"}
J -->|"yes"| C{"a[j] > a[j+1] ?"}
C -->|"yes"| SW["swap a[j], a[j+1]<br/>swapped = true"] --> NJ["j = j + 1"]
C -->|"no"| NJ
NJ --> J
J -->|"no"| E{"swapped ?"}
E -->|"no: already sorted"| D
E -->|"yes"| NI["i = i + 1"] --> P
Pass (0-based) compares positions . The comparison is strict (>), so two equal elements are never swapped; that single character is what makes bubble sort stable.
Trace on [5, 1, 4, 2, 8, 3] (computed by script; this input has 7 inversions):
| Pass | Comparisons | Swaps | Array after the pass | Now in final position |
|---|---|---|---|---|
| 1 | 5 | 4 | [1, 4, 2, 5, 3, 8] | 8 |
| 2 | 4 | 2 | [1, 2, 4, 3, 5, 8] | 5, 8 |
| 3 | 3 | 1 | [1, 2, 3, 4, 5, 8] | 4, 5, 8 |
| 4 | 2 | 0 | [1, 2, 3, 4, 5, 8] | no swaps: stop |
Total: 14 comparisons and 7 swaps — exactly the 7 inversions, as fact 3 predicts. Without the early exit the algorithm would run a fifth pass with 1 more comparison. Notice that pass 1 also moved 1 from index 1 to index 0 and pass 3 placed 3, 4 and the rest: elements move left by at most one position per pass ("turtles") but right by arbitrarily many ("rabbits"). A small element near the end is what makes bubble sort slow — it needs one full pass per position it must travel.
Selection sort
For each from 0 to : scan a[i..n-1] for the index of the minimum, then swap a[i] with a[m] (skip the swap if ). The scan uses strict <, so among equal minima it picks the leftmost — which does not make the algorithm stable, as the stability section shows.
Trace on [5, 2, 4, 6, 1, 3]:
| i | Scan range | Comparisons | Min index | a[m] | Swap? | Array after |
|---|---|---|---|---|---|---|
| 0 | a[0..5] | 5 | 4 | 1 | a[0] ↔ a[4] | [1, 2, 4, 6, 5, 3] |
| 1 | a[1..5] | 4 | 1 | 2 | no () | [1, 2, 4, 6, 5, 3] |
| 2 | a[2..5] | 3 | 5 | 3 | a[2] ↔ a[5] | [1, 2, 3, 6, 5, 4] |
| 3 | a[3..5] | 2 | 5 | 4 | a[3] ↔ a[5] | [1, 2, 3, 4, 5, 6] |
| 4 | a[4..5] | 1 | 4 | 5 | no | [1, 2, 3, 4, 5, 6] |
Total: 15 comparisons — always , whatever the input — and 3 swaps. The array was sorted after row 3, but selection sort cannot know that: it has no early exit, because a scan for a minimum tells you nothing about whether the rest is in order.
Insertion sort
flowchart TD
S["i = 1"] --> L{"i < n ?"}
L -->|"no"| D["done: a is sorted"]
L -->|"yes"| K["key = a[i]<br/>j = i - 1"]
K --> W{"j >= 0 and a[j] > key ?"}
W -->|"yes"| SH["a[j+1] = a[j] (shift right)<br/>j = j - 1"] --> W
W -->|"no"| PUT["a[j+1] = key"]
PUT --> NI["i = i + 1"] --> L
The inner loop does not swap; it shifts. It holds the key in a register, copies each larger element one place right, and writes the key once at the end. A shift is one memory write, a swap is three, so this is about a third of the writes of a swap-based version — the reason textbook insertion sort is written this way.
Trace on [5, 2, 4, 6, 1, 3] (9 inversions; computed by script):
| i | key | Comparisons | Shifts | Key lands at | Array after | Sorted prefix |
|---|---|---|---|---|---|---|
| 1 | 2 | 1 | 1 | 0 | [2, 5, 4, 6, 1, 3] | a[0..1] |
| 2 | 4 | 2 | 1 | 1 | [2, 4, 5, 6, 1, 3] | a[0..2] |
| 3 | 6 | 1 | 0 | 3 | [2, 4, 5, 6, 1, 3] | a[0..3] |
| 4 | 1 | 4 | 4 | 0 | [1, 2, 4, 5, 6, 3] | a[0..4] |
| 5 | 3 | 4 | 3 | 2 | [1, 2, 3, 4, 5, 6] | a[0..5] |
Totals: 12 comparisons, 9 shifts. The shifts equal the inversions, row by row: the key 1 in row 4 is preceded by four larger elements (5, 2, 4, 6 in the original array), so it causes four shifts. The comparisons are the shifts plus one failed comparison per key — except for keys that travel all the way to index 0 (rows 1 and 4), where the loop stops on j >= 0 without a failed comparison. That is the exact formula proved in Complexity: with here.
Stability
Definition. A sort is stable if any two elements with equal keys appear in the output in the same relative order as in the input.
Stability only means something when elements carry more than their key — records sorted by one field. Here are four records, keyed by the number, with a letter to tell them apart: [(4,a), (2,b), (4,c), (1,d)]. The two 4s start in the order a, c.
Insertion sort, step by step:
| i | key | Comparisons and shifts | Array after |
|---|---|---|---|
| 1 | (2,b) | (4,a) > 2: shift | [(2,b), (4,a), (4,c), (1,d)] |
| 2 | (4,c) | (4,a) > 4? no (equal): stop | [(2,b), (4,a), (4,c), (1,d)] |
| 3 | (1,d) | three shifts | [(1,d), (2,b), (4,a), (4,c)] |
The 4s are still in order a, c: stable. The decisive row is : the inner loop moves an element only when it is strictly greater than the key, so a key never jumps over an equal one.
Selection sort on the same input:
| i | Minimum of the rest | Swap | Array after |
|---|---|---|---|
| 0 | (1,d) at index 3 | a[0] ↔ a[3] | [(1,d), (2,b), (4,c), (4,a)] |
| 1 | (2,b) at index 1 | none | [(1,d), (2,b), (4,c), (4,a)] |
| 2 | (4,c) at index 2 (not beaten by (4,a)) | none | [(1,d), (2,b), (4,c), (4,a)] |
Now c comes before a: unstable. The long-distance swap in row 0 threw (4,a) from the front of the array to the back, over (4,c). Any sort that swaps non-adjacent elements is at risk of this; selection sort, Shell sort, heap sort and the usual quicksort are all unstable.
flowchart LR
IN["input:<br/>(4,a) (2,b) (4,c) (1,d)"] --> INS["insertion sort<br/>(only moves strictly larger)"]
IN --> SEL["selection sort<br/>(long-distance swap)"]
INS --> OUT1["(1,d) (2,b) (4,a) (4,c)<br/>stable"]
SEL --> OUT2["(1,d) (2,b) (4,c) (4,a)<br/>unstable"]
Why stability matters.
- Multi-key sorting in passes. To sort employees by department and, within a department, by salary, sort by salary first and then stable-sort by department; the second sort keeps the salary order inside each department. Clicking column headers in a data grid works this way: the previous order survives as the tie-breaker.
- Radix sort depends on it. LSD radix sort sorts by the last digit, then the second-to-last, and so on; an unstable pass would destroy the order set by earlier digits. See Non-Comparison Sorts.
- Predictable output. Log events sorted by severity should stay in time order within a severity. An unstable sort's tie order depends on algorithm internals and can change between library versions.
Getting stability back. Any sort becomes stable if you sort pairs (key, original_index): ties are broken by the index. The cost is extra memory and a dearer comparison. Memorise which built-ins are stable: Python's sorted and list.sort, Java's Arrays.sort on object arrays and Collections.sort (primitives use a non-stable quicksort, where stability is meaningless), C++ std::stable_sort but not std::sort, and JavaScript's Array.prototype.sort since ES2019.
The ladder: brute force → better → optimal
The task: sort an array of comparable elements in place.
Rung 0 — permutation sort, . Try every permutation and return the first sorted one. Useless beyond ( permutations), but obviously correct, which makes it a perfect test oracle for tiny inputs.
Rung 1 — selection sort, always. Each position costs one scan of the rest: exactly comparisons on every input, at most swaps. The improvement over rung 0 is the observation that the element for position 0 can be found (it is the minimum) instead of guessed. Its weakness is that it is oblivious: a sorted array costs as much as a random one.
Rung 2 — bubble sort with early exit, worst, best. Early exit makes it adaptive: a sorted array costs one pass of comparisons. But small elements move left only one position per pass, so [2, 3, 4, …, n, 1] forces passes and comparisons with only inversions. On random input early exit saves less than 1%.
Rung 3 — insertion sort, . Exactly shifts and at most comparisons: the cost tracks the actual disorder. [2, 3, 4, …, n, 1] costs shifts. On random input it makes about comparisons, half of selection sort's. Among the elementary sorts it dominates.
Rung 4 — binary insertion sort, comparisons, moves. The sorted prefix can be searched with binary search instead of a linear scan. That cuts comparisons to , which for is 8,977 against the information-theoretic minimum — near-optimal. Moves stay . This wins when comparisons are expensive and moves are a cheap memmove of pointers — Timsort's situation.
Rung 5 — Shell sort, subquadratic. Each insertion-sort shift fixes one inversion. Shell sort first insertion-sorts elements apart for decreasing gaps , so one move fixes many inversions, then finishes with on an almost sorted array. Worst case with Sedgewick's gaps; on 10,000 random integers, 190,850 comparisons (Ciura gaps) against insertion sort's 24,976,256.
Rung 6 — sorts. Merge sort, quicksort and heap sort reach the comparison lower bound up to a constant. They are the next three lessons.
| Rung | Comparisons (worst) | Comparisons (sorted input) | Moves (worst) | Stable | Adaptive | Extra space |
|---|---|---|---|---|---|---|
| Permutation sort | — | depends | — | |||
| Selection | swaps | no | no | |||
| Bubble (early exit) | swaps | yes | yes | |||
| Insertion | shifts | yes | yes, | |||
| Binary insertion | shifts | yes | moves only | |||
| Shell (good gaps) | (Sedgewick) | same order | no | somewhat |
Correctness
Each proof below has the same shape: an invariant that holds before every iteration of the outer loop, a check that each iteration preserves it, and an argument that the invariant at termination means "sorted". Each algorithm also only rearranges elements (swaps or shifts that move the key), so the output is a permutation of the input; that half of "sorts correctly" is immediate and not repeated.
Bubble sort
Invariant : before pass (0-based), the suffix a[n-i..n-1] holds the largest elements of the array, in sorted order, and every element of a[0..n-i-1] is every element of that suffix.
Initialisation. For the suffix is empty.
Maintenance. Pass scans . Claim: after comparing positions and , a[j+1] is the maximum of a[0..j+1]. For this holds because the larger of the two ends up at position 1. If it holds after step , then a[j] is the maximum of a[0..j] and the compare-and-swap puts a[j], a[j+1] at position . So after the pass, a[n-1-i] is the maximum of a[0..n-1-i], which by is the -th largest element overall and is everything in the old suffix. The suffix grows by one and stays sorted.
Termination. After passes the suffix a[1..n-1] holds the largest elements in order and a[0] is all of them: sorted.
Early exit lemma. If a pass makes no swaps, every comparison in it found a[j] <= a[j+1] for , so the prefix a[0..n-1-i] is sorted; by its elements are all the sorted suffix. The whole array is sorted, and stopping is correct.
Stability. Bubble sort only swaps adjacent elements with a[j] > a[j+1], strictly. Two equal elements are never swapped with each other, and swaps with other elements never change their relative order (fact 3: an adjacent swap changes the relative order of exactly the two swapped elements). Their order is preserved.
Swaps = inversions. Every swap is of an adjacent inverted pair and removes exactly one inversion (fact 3); the algorithm stops with zero inversions. So the number of swaps is exactly .
Selection sort
Invariant : before iteration , a[0..i-1] holds the smallest elements in sorted order, and every element of a[0..i-1] is every element of a[i..n-1].
Maintenance. Iteration finds the index of a minimum of a[i..n-1] and swaps it into position . By , that minimum is everything in a[0..i-1], so a[0..i] is sorted, and it is everything left in a[i+1..n-1]. holds for .
Termination. After iteration , a[0..n-2] holds the smallest elements in order and a[n-1] is all of them.
Rotating the minimum into place instead of swapping makes selection sort stable, at the price of writes — its one advantage gone.
Insertion sort
Outer invariant : before iteration (), a[0..i-1] consists of the elements originally in positions , in sorted order.
Inner invariant (for fixed , at each test of the while condition): key is the original a[i]; the elements originally in a[0..i-1] now occupy a[0..j] and a[j+2..i] in sorted order, with a[j+1] a free "hole"; and every element in a[j+2..i] is strictly greater than key.
Initialisation of . With j = i - 1, the sorted prefix sits in a[0..i-1], a[i] (copied into key) is the hole, and a[j+2..i] is empty.
Maintenance of . If a[j] > key, the loop copies a[j] into the hole at j + 1 and decrements j; the hole moves one place left, the moved element is greater than key, and order is unchanged.
Exit of the inner loop. Either j = -1 (everything in the prefix is key) or a[j] <= key. In both cases writing key into the hole a[j+1] gives a[0..j] <= key < a[j+2..i], with both sides sorted: a[0..i] is the original first elements in sorted order. That is for .
Termination. with says the whole array is sorted.
Stability. The inner loop moves an element past the key only when it is strictly greater. An element equal to the key stops the loop, so the key is placed after it: equal elements keep their original order.
Theorem: insertion sort performs exactly shifts
Proof. Fix iteration . By , the prefix a[0..i-1] is a rearrangement of the original elements at positions . The inner loop shifts exactly the prefix elements that are strictly greater than key (they form a contiguous block at the end of the sorted prefix, and the loop stops at the first element that is not greater). So the number of shifts in iteration equals
the number of inversions whose second element is at original position . Every inversion has exactly one second element, so summing over counts every inversion exactly once: .
This gives a clean interpretation of the trace table: the "Shifts" column is, for each element, the number of larger elements to its left in the original array. That column's sum is the inversion count, and the next lesson computes it in without sorting quadratically.
Corollary (lower bound for adjacent-swap sorts). Any algorithm that sorts by exchanging adjacent elements must perform at least exchanges, because each exchange removes at most one inversion. On average that is ; in the worst case . So every adjacent-exchange sort is on average. To beat you must move elements over long distances — which is exactly what Shell sort, merge sort and quicksort do.
Complexity
All counts below are exact for arrays of distinct elements and were checked by enumerating every permutation of size (and by random sampling for larger ). is the -th harmonic number.
| Algorithm | Measure | Best | Average | Worst |
|---|---|---|---|---|
| Bubble (early exit) | comparisons | (see below) | ||
| Bubble | swaps | 0 | ||
| Selection | comparisons | |||
| Selection | swaps (skipping ) | 0 | ||
| Insertion | comparisons | |||
| Insertion | shifts | 0 |
Insertion sort, exactly
Each iteration makes comparisons that succeed (each followed by a shift) plus one comparison that fails — unless the key travels all the way to index 0, in which case the loop ends on j >= 0 with no failed comparison. Let be the number of positions whose element is smaller than every element before it (a new left-to-right minimum). Then
- Best case (sorted input): , , so and zero shifts.
- Worst case (strictly decreasing): and every element is a new minimum, , so . For , 28 comparisons.
- Average case (random permutation): , and position (0-based) holds a new minimum with probability , so . Hence . For this is , which matches the brute-force average over all 40,320 permutations exactly.
The honest summary is time: insertion sort is adaptive — its cost depends on the disorder of the input, not just its size. Special cases:
- Every element within distance of its sorted position: two elements more than positions apart cannot be inverted, so and insertion sort is .
- 50 random adjacent swaps applied to a sorted array of 10,000: measured 10,049 comparisons, against about 25 million for a random array.
Selection sort, exactly
Comparisons are on every input — no best case. Swaps (skipping ): exactly for a permutation with cycles, because each swap splits one element off into a cycle of its own; the average number of cycles is , giving . The running minimum is updated times on average (Knuth, Vol. 3, §5.2.3) — bookkeeping, dominated by the comparisons.
Selection sort's real distinction is writes: in total, fewer than the others. Cycle sort goes further and writes each element at most once.
Bubble sort, exactly
Swaps equal , averaging . Pass makes comparisons, and Knuth (Vol. 3, §5.2.2) shows the average number of passes is : early exit skips only about passes, all short ones. Measured at : 961.4 passes on average (formula 960.4) and 498,577 comparisons against the worst case 499,500. On random input early exit saves less than 0.2%.
Space
All three sort in place with extra memory: a loop index or two, a temporary for a swap, the key. None is recursive.
Constants and cache behaviour
Big-O hides why insertion sort is fast on small arrays. Its inner loop is one load, one compare, one store and one decrement; it walks memory sequentially, which prefetchers handle well; and a small array sits in L1 cache at about 1 ns per load. There is no recursion, no auxiliary buffer and no pivot bookkeeping — the overheads that dominate merge sort and quicksort on 16 elements. That is why every production hybrid switches to insertion sort below some threshold, and why the threshold is found by benchmarking, not derived.
Branch prediction cuts the other way for selection sort: its minimum-update branch is taken only about times per scan on random data, so it predicts well, and selection sort is less far behind insertion sort in wall-clock time on small random arrays than the comparison counts suggest. Measure before trusting either intuition; see Benchmarks and How Data Structures Live in Memory.
Implementation
The canonical block implements the five sorts generically with a comparator, returns the operation counts that the proofs talk about (swaps for bubble and selection, shifts for insertion), and checks: the trace inputs, edge cases, the inversion theorem, the stability demonstration from the Mechanics section, and a randomised comparison against the built-in sort.
import bisect
import random
from typing import Any, Callable
def identity(x: Any) -> Any:
return x
def bubble_sort(a: list, key: Callable = identity) -> int:
"""Sort a in place (stable). Return the number of swaps, which equals the inversion count."""
n, swaps = len(a), 0
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if key(a[j]) > key(a[j + 1]): # strict: equal keys never swap -> stable
a[j], a[j + 1] = a[j + 1], a[j]
swaps += 1
swapped = True
if not swapped: # early exit: a pass with no swaps means sorted
break
return swaps
def selection_sort(a: list, key: Callable = identity) -> int:
"""Sort a in place (NOT stable). Return the number of swaps (at most n - 1)."""
n, swaps = len(a), 0
for i in range(n - 1):
m = i
for j in range(i + 1, n):
if key(a[j]) < key(a[m]):
m = j
if m != i:
a[i], a[m] = a[m], a[i]
swaps += 1
return swaps
def insertion_sort(a: list, key: Callable = identity) -> int:
"""Sort a in place (stable). Return the number of shifts, which equals the inversion count."""
shifts = 0
for i in range(1, len(a)):
item = a[i]
k = key(item)
j = i - 1
while j >= 0 and key(a[j]) > k: # strict > keeps equal keys in order
a[j + 1] = a[j] # shift, do not swap
j -= 1
shifts += 1
a[j + 1] = item
return shifts
def binary_insertion_sort(a: list, key: Callable = identity) -> None:
"""Stable; O(n log n) comparisons, O(n^2) moves."""
for i in range(1, len(a)):
item = a[i]
pos = bisect.bisect_right(a, key(item), 0, i, key=key) # after any equal keys -> stable
a[pos + 1:i + 1] = a[pos:i] # one block move (memmove)
a[pos] = item
def ciura_gaps(n: int) -> list[int]:
gaps = [1, 4, 10, 23, 57, 132, 301, 701]
while gaps[-1] * 9 // 4 < n: # extend by about 2.25x
gaps.append(gaps[-1] * 9 // 4)
return [g for g in reversed(gaps) if g < n] or [1]
def shell_sort(a: list, key: Callable = identity) -> None:
"""Gapped insertion sort with Ciura's gaps. NOT stable."""
n = len(a)
for g in ciura_gaps(n):
for i in range(g, n):
item = a[i]
k = key(item)
j = i
while j >= g and key(a[j - g]) > k:
a[j] = a[j - g]
j -= g
a[j] = item
def inversions_naive(a: list) -> int:
return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])
ALL = [bubble_sort, selection_sort, insertion_sort, binary_insertion_sort, shell_sort]
if __name__ == "__main__":
base = [5, 2, 4, 6, 1, 3]
for sort in ALL:
for data in ([], [7], [2, 2, 2], base, [5, 1, 4, 2, 8, 3], list(range(8, 0, -1))):
b = list(data)
sort(b)
assert b == sorted(data), (sort.__name__, data, b)
# Operation counts from the trace tables and the proofs.
assert inversions_naive(base) == 9
assert insertion_sort(list(base)) == 9 == bubble_sort(list(base))
assert bubble_sort([5, 1, 4, 2, 8, 3]) == 7
assert selection_sort(list(base)) == 3
assert insertion_sort(list(range(8, 0, -1))) == 28 # reversed: n(n-1)/2
assert insertion_sort(list(range(10))) == 0 # sorted: no shifts
# Stability demonstration: records keyed by the number.
recs = [(4, "a"), (2, "b"), (4, "c"), (1, "d")]
first = lambda r: r[0]
for sort in (bubble_sort, insertion_sort, binary_insertion_sort):
b = list(recs)
sort(b, key=first)
assert b == [(1, "d"), (2, "b"), (4, "a"), (4, "c")], sort.__name__
b = list(recs)
selection_sort(b, key=first)
assert b == [(1, "d"), (2, "b"), (4, "c"), (4, "a")] # unstable
# Randomised check against the (stable) built-in sort.
rng = random.Random(42)
for _ in range(300):
n = rng.randint(0, 30)
data = [(rng.randint(0, 9), idx) for idx in range(n)] # many duplicate keys
expected = sorted(data, key=first)
for sort in ALL:
b = list(data)
sort(b, key=first)
if sort in (selection_sort, shell_sort):
assert [r[0] for r in b] == [r[0] for r in expected]
else:
assert b == expected, sort.__name__
keys = [r[0] for r in data]
assert insertion_sort(list(keys)) == inversions_naive(keys)
print("ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
public class ElementarySorts {
record Rec(int key, char tag) {}
static <T> int bubbleSort(T[] a, Comparator<? super T> c) {
int n = a.length, swaps = 0;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (c.compare(a[j], a[j + 1]) > 0) { // strict: equal keys never swap
T t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swaps++;
swapped = true;
}
}
if (!swapped) break; // early exit
}
return swaps;
}
static <T> int selectionSort(T[] a, Comparator<? super T> c) {
int n = a.length, swaps = 0;
for (int i = 0; i < n - 1; i++) {
int m = i;
for (int j = i + 1; j < n; j++) if (c.compare(a[j], a[m]) < 0) m = j;
if (m != i) { T t = a[i]; a[i] = a[m]; a[m] = t; swaps++; }
}
return swaps;
}
static <T> int insertionSort(T[] a, Comparator<? super T> c) {
int shifts = 0;
for (int i = 1; i < a.length; i++) {
T item = a[i];
int j = i - 1;
while (j >= 0 && c.compare(a[j], item) > 0) { // strict > keeps it stable
a[j + 1] = a[j];
j--;
shifts++;
}
a[j + 1] = item;
}
return shifts;
}
static <T> void binaryInsertionSort(T[] a, Comparator<? super T> c) {
for (int i = 1; i < a.length; i++) {
T item = a[i];
int lo = 0, hi = i; // first index in [0, i) with a[idx] > item
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (c.compare(a[mid], item) <= 0) lo = mid + 1; else hi = mid;
}
System.arraycopy(a, lo, a, lo + 1, i - lo); // one block move
a[lo] = item;
}
}
static List<Integer> ciuraGaps(int n) {
List<Integer> g = new ArrayList<>(List.of(1, 4, 10, 23, 57, 132, 301, 701));
while ((long) g.get(g.size() - 1) * 9 / 4 < n) g.add((int) ((long) g.get(g.size() - 1) * 9 / 4));
List<Integer> out = new ArrayList<>();
for (int k = g.size() - 1; k >= 0; k--) if (g.get(k) < n) out.add(g.get(k));
if (out.isEmpty()) out.add(1);
return out;
}
static <T> void shellSort(T[] a, Comparator<? super T> c) {
int n = a.length;
for (int g : ciuraGaps(n)) {
for (int i = g; i < n; i++) {
T item = a[i];
int j = i;
while (j >= g && c.compare(a[j - g], item) > 0) { a[j] = a[j - g]; j -= g; }
a[j] = item;
}
}
}
static int inversionsNaive(Integer[] a) {
int cnt = 0;
for (int i = 0; i < a.length; i++) for (int j = i + 1; j < a.length; j++) if (a[i] > a[j]) cnt++;
return cnt;
}
static void check(boolean ok, String msg) {
if (!ok) throw new AssertionError(msg);
}
static Integer[] box(int... xs) {
return Arrays.stream(xs).boxed().toArray(Integer[]::new);
}
public static void main(String[] args) {
Comparator<Integer> nat = Comparator.naturalOrder();
int[][] cases = {{}, {7}, {2, 2, 2}, {5, 2, 4, 6, 1, 3}, {5, 1, 4, 2, 8, 3}, {8, 7, 6, 5, 4, 3, 2, 1}};
for (int[] cs : cases) {
Integer[] expected = box(cs);
Arrays.sort(expected);
for (int s = 0; s < 5; s++) {
Integer[] b = box(cs);
switch (s) {
case 0 -> bubbleSort(b, nat);
case 1 -> selectionSort(b, nat);
case 2 -> insertionSort(b, nat);
case 3 -> binaryInsertionSort(b, nat);
default -> shellSort(b, nat);
}
check(Arrays.equals(b, expected), "sort " + s + " failed on " + Arrays.toString(cs));
}
}
check(inversionsNaive(box(5, 2, 4, 6, 1, 3)) == 9, "inversions");
check(insertionSort(box(5, 2, 4, 6, 1, 3), nat) == 9, "insertion shifts");
check(bubbleSort(box(5, 2, 4, 6, 1, 3), nat) == 9, "bubble swaps");
check(bubbleSort(box(5, 1, 4, 2, 8, 3), nat) == 7, "bubble swaps 2");
check(selectionSort(box(5, 2, 4, 6, 1, 3), nat) == 3, "selection swaps");
check(insertionSort(box(8, 7, 6, 5, 4, 3, 2, 1), nat) == 28, "reversed");
check(insertionSort(box(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), nat) == 0, "sorted");
Comparator<Rec> byKey = Comparator.comparingInt(Rec::key);
Rec[] recs = {new Rec(4, 'a'), new Rec(2, 'b'), new Rec(4, 'c'), new Rec(1, 'd')};
Rec[] stable = {new Rec(1, 'd'), new Rec(2, 'b'), new Rec(4, 'a'), new Rec(4, 'c')};
Rec[] b1 = recs.clone(); bubbleSort(b1, byKey); check(Arrays.equals(b1, stable), "bubble stable");
Rec[] b2 = recs.clone(); insertionSort(b2, byKey); check(Arrays.equals(b2, stable), "insertion stable");
Rec[] b3 = recs.clone(); binaryInsertionSort(b3, byKey); check(Arrays.equals(b3, stable), "binins stable");
Rec[] b4 = recs.clone(); selectionSort(b4, byKey);
check(Arrays.equals(b4, new Rec[]{new Rec(1, 'd'), new Rec(2, 'b'), new Rec(4, 'c'), new Rec(4, 'a')}),
"selection unstable");
Random rng = new Random(42);
for (int t = 0; t < 300; t++) {
int n = rng.nextInt(31);
Rec[] data = new Rec[n];
for (int i = 0; i < n; i++) data[i] = new Rec(rng.nextInt(10), (char) ('A' + i));
Rec[] expected = data.clone();
Arrays.sort(expected, byKey); // TimSort: stable
for (int s = 0; s < 5; s++) {
Rec[] b = data.clone();
switch (s) {
case 0 -> bubbleSort(b, byKey);
case 1 -> selectionSort(b, byKey);
case 2 -> insertionSort(b, byKey);
case 3 -> binaryInsertionSort(b, byKey);
default -> shellSort(b, byKey);
}
for (int i = 0; i < n; i++) {
check(b[i].key() == expected[i].key(), "keys differ");
if (s == 0 || s == 2 || s == 3) check(b[i].equals(expected[i]), "not stable");
}
}
Integer[] keys = new Integer[n];
for (int i = 0; i < n; i++) keys[i] = data[i].key();
check(insertionSort(keys.clone(), nat) == inversionsNaive(keys), "shifts != inversions");
}
System.out.println("ok");
}
}
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
// comp(x, y) is true when x must come before y (a strict "less than").
template <class T, class Comp = std::less<T>>
long long bubbleSort(std::vector<T>& a, Comp comp = Comp{}) {
long long swaps = 0;
const std::size_t n = a.size();
for (std::size_t i = 0; i + 1 < n; ++i) {
bool swapped = false;
for (std::size_t j = 0; j + 1 < n - i; ++j) {
if (comp(a[j + 1], a[j])) { // a[j] > a[j+1], strictly
std::swap(a[j], a[j + 1]);
++swaps;
swapped = true;
}
}
if (!swapped) break;
}
return swaps;
}
template <class T, class Comp = std::less<T>>
long long selectionSort(std::vector<T>& a, Comp comp = Comp{}) {
long long swaps = 0;
const std::size_t n = a.size();
for (std::size_t i = 0; i + 1 < n; ++i) {
std::size_t m = i;
for (std::size_t j = i + 1; j < n; ++j)
if (comp(a[j], a[m])) m = j;
if (m != i) { std::swap(a[i], a[m]); ++swaps; }
}
return swaps;
}
template <class T, class Comp = std::less<T>>
long long insertionSort(std::vector<T>& a, Comp comp = Comp{}) {
long long shifts = 0;
for (std::size_t i = 1; i < a.size(); ++i) {
T item = std::move(a[i]);
std::size_t j = i; // j is the hole; compare a[j-1]
while (j > 0 && comp(item, a[j - 1])) { // a[j-1] > item, strictly
a[j] = std::move(a[j - 1]);
--j;
++shifts;
}
a[j] = std::move(item);
}
return shifts;
}
template <class T, class Comp = std::less<T>>
void binaryInsertionSort(std::vector<T>& a, Comp comp = Comp{}) {
for (std::size_t i = 1; i < a.size(); ++i) {
auto pos = std::upper_bound(a.begin(), a.begin() + i, a[i], comp); // after equal keys
std::rotate(pos, a.begin() + i, a.begin() + i + 1); // block move
}
}
std::vector<std::size_t> ciuraGaps(std::size_t n) {
std::vector<std::size_t> g{1, 4, 10, 23, 57, 132, 301, 701};
while (g.back() * 9 / 4 < n) g.push_back(g.back() * 9 / 4);
std::vector<std::size_t> out;
for (auto it = g.rbegin(); it != g.rend(); ++it)
if (*it < n) out.push_back(*it);
if (out.empty()) out.push_back(1);
return out;
}
template <class T, class Comp = std::less<T>>
void shellSort(std::vector<T>& a, Comp comp = Comp{}) {
const std::size_t n = a.size();
for (std::size_t g : ciuraGaps(n)) {
for (std::size_t i = g; i < n; ++i) {
T item = std::move(a[i]);
std::size_t j = i;
while (j >= g && comp(item, a[j - g])) { a[j] = std::move(a[j - g]); j -= g; }
a[j] = std::move(item);
}
}
}
long long inversionsNaive(const std::vector<int>& a) {
long long c = 0;
for (std::size_t i = 0; i < a.size(); ++i)
for (std::size_t j = i + 1; j < a.size(); ++j)
if (a[i] > a[j]) ++c;
return c;
}
struct Rec {
int key;
char tag;
bool operator==(const Rec&) const = default;
};
int main() {
std::vector<std::vector<int>> cases{{}, {7}, {2, 2, 2}, {5, 2, 4, 6, 1, 3}, {5, 1, 4, 2, 8, 3},
{8, 7, 6, 5, 4, 3, 2, 1}};
for (const auto& cs : cases) {
auto expected = cs;
std::sort(expected.begin(), expected.end());
for (int s = 0; s < 5; ++s) {
auto b = cs;
if (s == 0) bubbleSort(b);
else if (s == 1) selectionSort(b);
else if (s == 2) insertionSort(b);
else if (s == 3) binaryInsertionSort(b);
else shellSort(b);
assert(b == expected);
if (b != expected) return 1;
}
}
std::vector<int> base{5, 2, 4, 6, 1, 3};
auto t1 = base, t2 = base, t3 = base;
std::vector<int> bub{5, 1, 4, 2, 8, 3}, rev{8, 7, 6, 5, 4, 3, 2, 1}, srt{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
bool ok = inversionsNaive(base) == 9 && insertionSort(t1) == 9 && bubbleSort(t2) == 9 &&
bubbleSort(bub) == 7 && selectionSort(t3) == 3 && insertionSort(rev) == 28 && insertionSort(srt) == 0;
if (!ok) { std::cerr << "count check failed\n"; return 1; }
auto byKey = [](const Rec& x, const Rec& y) { return x.key < y.key; };
std::vector<Rec> recs{{4, 'a'}, {2, 'b'}, {4, 'c'}, {1, 'd'}};
std::vector<Rec> stable{{1, 'd'}, {2, 'b'}, {4, 'a'}, {4, 'c'}};
std::vector<Rec> unstable{{1, 'd'}, {2, 'b'}, {4, 'c'}, {4, 'a'}};
auto r1 = recs, r2 = recs, r3 = recs, r4 = recs;
bubbleSort(r1, byKey); insertionSort(r2, byKey); binaryInsertionSort(r3, byKey); selectionSort(r4, byKey);
if (r1 != stable || r2 != stable || r3 != stable || r4 != unstable) { std::cerr << "stability\n"; return 1; }
std::mt19937 rng(42);
for (int t = 0; t < 300; ++t) {
int n = static_cast<int>(rng() % 31);
std::vector<Rec> data;
for (int i = 0; i < n; ++i) data.push_back({static_cast<int>(rng() % 10), static_cast<char>('A' + i)});
auto expected = data;
std::stable_sort(expected.begin(), expected.end(), byKey);
for (int s = 0; s < 5; ++s) {
auto b = data;
if (s == 0) bubbleSort(b, byKey);
else if (s == 1) selectionSort(b, byKey);
else if (s == 2) insertionSort(b, byKey);
else if (s == 3) binaryInsertionSort(b, byKey);
else shellSort(b, byKey);
for (int i = 0; i < n; ++i) {
if (b[i].key != expected[i].key) { std::cerr << "keys differ\n"; return 1; }
if ((s == 0 || s == 2 || s == 3) && !(b[i] == expected[i])) { std::cerr << "unstable\n"; return 1; }
}
}
std::vector<int> keys;
for (const auto& r : data) keys.push_back(r.key);
auto k2 = keys;
if (insertionSort(k2) != inversionsNaive(keys)) { std::cerr << "shifts != inversions\n"; return 1; }
}
std::cout << "ok\n";
return 0;
}
type Cmp<T> = (x: T, y: T) => number; // negative: x before y; zero: equal keys
function bubbleSort<T>(a: T[], c: Cmp<T>): number {
const n = a.length;
let swaps = 0;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (c(a[j], a[j + 1]) > 0) { // strict: equal keys never swap
[a[j], a[j + 1]] = [a[j + 1], a[j]];
swaps++;
swapped = true;
}
}
if (!swapped) break; // early exit
}
return swaps;
}
function selectionSort<T>(a: T[], c: Cmp<T>): number {
const n = a.length;
let swaps = 0;
for (let i = 0; i < n - 1; i++) {
let m = i;
for (let j = i + 1; j < n; j++) if (c(a[j], a[m]) < 0) m = j;
if (m !== i) {
[a[i], a[m]] = [a[m], a[i]];
swaps++;
}
}
return swaps;
}
function insertionSort<T>(a: T[], c: Cmp<T>): number {
let shifts = 0;
for (let i = 1; i < a.length; i++) {
const item = a[i];
let j = i - 1;
while (j >= 0 && c(a[j], item) > 0) { // strict > keeps it stable
a[j + 1] = a[j];
j--;
shifts++;
}
a[j + 1] = item;
}
return shifts;
}
function binaryInsertionSort<T>(a: T[], c: Cmp<T>): void {
for (let i = 1; i < a.length; i++) {
const item = a[i];
let lo = 0;
let hi = i; // first index in [0, i) with a[idx] > item
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (c(a[mid], item) <= 0) lo = mid + 1;
else hi = mid;
}
a.copyWithin(lo + 1, lo, i); // one block move
a[lo] = item;
}
}
function ciuraGaps(n: number): number[] {
const g = [1, 4, 10, 23, 57, 132, 301, 701];
while (Math.floor((g[g.length - 1] * 9) / 4) < n) g.push(Math.floor((g[g.length - 1] * 9) / 4));
const out = g.filter((x) => x < n).reverse();
return out.length > 0 ? out : [1];
}
function shellSort<T>(a: T[], c: Cmp<T>): void {
const n = a.length;
for (const g of ciuraGaps(n)) {
for (let i = g; i < n; i++) {
const item = a[i];
let j = i;
while (j >= g && c(a[j - g], item) > 0) {
a[j] = a[j - g];
j -= g;
}
a[j] = item;
}
}
}
function inversionsNaive(a: number[]): number {
let cnt = 0;
for (let i = 0; i < a.length; i++) for (let j = i + 1; j < a.length; j++) if (a[i] > a[j]) cnt++;
return cnt;
}
function check(ok: boolean, msg: string): void {
if (!ok) throw new Error(msg);
}
const num: Cmp<number> = (x, y) => x - y;
const sorts = [bubbleSort, selectionSort, insertionSort, binaryInsertionSort, shellSort];
const cases: number[][] = [[], [7], [2, 2, 2], [5, 2, 4, 6, 1, 3], [5, 1, 4, 2, 8, 3], [8, 7, 6, 5, 4, 3, 2, 1]];
for (const cs of cases) {
const expected = [...cs].sort(num);
for (const sort of sorts) {
const b = [...cs];
sort(b, num);
check(JSON.stringify(b) === JSON.stringify(expected), `${sort.name} failed on ${cs}`);
}
}
check(inversionsNaive([5, 2, 4, 6, 1, 3]) === 9, "inversions");
check(insertionSort([5, 2, 4, 6, 1, 3], num) === 9, "insertion shifts");
check(bubbleSort([5, 2, 4, 6, 1, 3], num) === 9, "bubble swaps");
check(bubbleSort([5, 1, 4, 2, 8, 3], num) === 7, "bubble swaps 2");
check(selectionSort([5, 2, 4, 6, 1, 3], num) === 3, "selection swaps");
check(insertionSort([8, 7, 6, 5, 4, 3, 2, 1], num) === 28, "reversed");
check(insertionSort([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], num) === 0, "sorted");
type Rec = [number, string];
const byKey: Cmp<Rec> = (x, y) => x[0] - y[0];
const recs: Rec[] = [[4, "a"], [2, "b"], [4, "c"], [1, "d"]];
const stable = JSON.stringify([[1, "d"], [2, "b"], [4, "a"], [4, "c"]]);
for (const sort of [bubbleSort, insertionSort, binaryInsertionSort]) {
const b = recs.map((r) => [...r] as Rec);
sort(b, byKey);
check(JSON.stringify(b) === stable, `${sort.name} not stable`);
}
const sel = recs.map((r) => [...r] as Rec);
selectionSort(sel, byKey);
check(JSON.stringify(sel) === JSON.stringify([[1, "d"], [2, "b"], [4, "c"], [4, "a"]]), "selection");
let seed = 42;
const rand = (m: number): number => {
seed = (seed * 1103515245 + 12345) % 2147483648;
return seed % m;
};
for (let t = 0; t < 300; t++) {
const n = rand(31);
const data: Rec[] = [];
for (let i = 0; i < n; i++) data.push([rand(10), String.fromCharCode(65 + i)]);
const expected = [...data].sort(byKey); // stable since ES2019
for (const sort of sorts) {
const b = [...data];
sort(b, byKey);
const stableSort = sort !== selectionSort && sort !== shellSort;
for (let i = 0; i < n; i++) {
check(b[i][0] === expected[i][0], "keys differ");
if (stableSort) check(b[i] === expected[i], `${sort.name} not stable`);
}
}
const keys = data.map((r) => r[0]);
check(insertionSort([...keys], num) === inversionsNaive(keys), "shifts != inversions");
}
console.log("ok");
The randomised test uses keys 0–9 so duplicates are everywhere: change one > to >= and the stability assertions fail at once. Python's bisect takes key= since 3.10; the value searched for is the key, not the element.
Variant: insertion sort with a sentinel
# fragment — the sentinel trick, shown for the idea only
def insertion_sort_sentinel(a):
m = min(range(len(a)), key=a.__getitem__) # move the minimum to the front first
a[0], a[m] = a[m], a[0] # (this one swap breaks stability)
for i in range(2, len(a)):
item, j = a[i], i - 1
while a[j] > item: # no j >= 0 test: a[0] stops the loop
a[j + 1] = a[j]
j -= 1
a[j + 1] = item
With the minimum at index 0 the inner loop can drop its bounds check, saving one compare-and-branch per shift (an exercise in Sedgewick and Wayne). The cost is an extra pass and a long-distance swap that breaks stability unless you rotate instead. The win on modern hardware is small; measure it.
Variant: Shell sort and its gaps
Shell sort (Donald Shell, 1959) is insertion sort applied to interleaved subsequences. For a gap , the array is -sorted if a[i] <= a[i+h] for all valid — the subsequences of elements apart are each sorted. Shell sort -sorts for a decreasing sequence of gaps ending in 1. The final pass is ordinary insertion sort, so correctness is immediate; the entire question is speed.
Two facts make it work. First, a large-gap pass moves an element positions per shift, removing up to inversions at once instead of one. Second, an -sorted array stays -sorted after it is -sorted (Knuth, Vol. 3, §5.2.1, Theorem K), so later passes do not undo the work of earlier ones and the final insertion sort runs on an array with few inversions.
| Gap sequence | Gaps | Worst case | Source |
|---|---|---|---|
| Shell (1959) | Shell, CACM 2(7), 1959 | ||
| Hibbard (1963) | Hibbard 1963; bound by Papernov & Stasevich 1965 | ||
| Knuth (1973) | Knuth Vol. 3 §5.2.1; Pratt 1971 | ||
| Pratt (1971) | all | Pratt, PhD thesis, Stanford, 1971 | |
| Sedgewick (1986) | Sedgewick, J. Algorithms 7(2), 1986 | ||
| Ciura (2001) | then | unknown (empirical) | Ciura, FCT 2001, LNCS 2138 |
Measured on one random permutation of 10,000 integers (comparisons): insertion sort 24,976,256; Shell's gaps 267,486; Knuth's gaps 241,454; Ciura's gaps 190,850; for scale, . Shell's original sequence has a bad worst case because all its gaps except the last can be even: on an array of 1,024 elements with the 512 largest values at even indices and the 512 smallest at odd indices, no pass before the last ever compares an even position with an odd one, and the final insertion sort does all the work — 140,544 comparisons, more than plain insertion sort's 132,350.
What is still open. Pratt's sequence gives worst case but has passes and is slow in practice. For the sequences that are fast in practice, the average-case complexity is unknown — not even its exponent. Plaxton, Poonen and Suel (FOCS 1992) proved that any fixed gap sequence has worst case , so Shell sort cannot reach worst case; whether some sequence achieves it on average is open. Ciura's gaps came from computer search, and the continuation beyond 701 is a heuristic, not a theorem.
Shell sort survives where code size and stack space matter more than the last factor of speed — it is short, in place and non-recursive — for example in some embedded C libraries' qsort. Treat any specific library claim as version-dependent.
Real-world uses
Inside every hybrid sort. The fast general-purpose sorts are all hybrids that hand small subproblems to insertion sort:
- Timsort (Tim Peters, 2002) — CPython's
list.sort, Java's objectArrays.sortandCollections.sort, V8'sArray.prototype.sortsince V8 7.0. It finds existing runs, and extends any natural run shorter thanminrun(between 32 and 64 in CPython) with binary insertion sort — chosen because Python comparisons are expensive method calls while moving pointers is a cheapmemmove. CPython 3.11 adopted Powersort's merge policy; run extension is unchanged. - Introsort —
std::sortin libstdc++ (and variants in libc++ and MSVC). Quicksort stops recursing on small partitions (16 elements in libstdc++), and one final insertion sort pass over the whole array finishes the job cheaply because every element is already inside its small partition. Heap sort is the fallback when recursion gets too deep. - pdqsort (Orson Peters, 2016) — Go's
sortsince Go 1.19, and the basis of Rust'ssort_unstableuntil Rust 1.81 replaced it. It insertion-sorts small partitions (24 elements in the reference implementation, 12 in Go) and adds a partial insertion sort: on a partition that did no swaps it tries insertion sort with a cap on moves, and if the cap is not hit the partition is done. Adaptivity bolted onto quicksort. - Java's dual-pivot quicksort for primitive arrays also uses insertion sort below a small threshold.
These thresholds are implementation details: found by benchmarking, different between libraries and changed between releases. Say "a few dozen elements" unless you cite a specific version. Sorting in the Real World opens up each of these.
Nearly sorted data. Timestamps merged from clocks with small skew, sensor readings that arrive slightly out of order, a sorted list after a few updates, objects sorted by depth for rendering that change little between frames: insertion sort re-sorts such data in close to linear time. Graphics engines have used one insertion or bubble pass per frame to keep a depth-ordered list approximately sorted.
Small fixed-size sorts. Median-of-three pivot selection, picking among a few candidates, maintaining a top-10 list: for 3 to 16 elements, insertion sort or a hand-written sorting network (a fixed sequence of compare-exchanges, which vectorises well) is the norm.
Database and query engines. Large sorts use an in-memory sort and external merge sort on disk (How Databases Work, Query Planning & Optimization). Stability matters at the SQL level in a negative way: ORDER BY promises nothing about rows that tie on the sort key, so add a unique tie-breaker column if the order matters.
Expensive moves. Selection sort's swaps and cycle sort's minimal writes matter when writes wear out the medium or elements are large records. Usually the better answer is to sort small references and move each record once.
Pitfalls & edge cases
>=versus>. Using>=in the insertion or bubble comparison breaks stability and wastes moves on equal elements. Using<=in selection sort's minimum search picks the last equal minimum, which makes it "more" unstable. Make the comparison strict and test with many duplicate keys.- Unsigned index underflow. In C/C++,
for (size_t j = i - 1; j >= 0; --j)never terminates becausej >= 0is always true for unsignedj. Track the hole index and testj > 0before readinga[j - 1], as the C++ block does. - Off-by-one in bubble sort's inner bound. The loop compares
a[j]witha[j+1], so the bound isj < n - 1 - i;j < n - ireads past the end. - Empty arrays.
range(n - 1)with is empty in Python, butn - 1withsize_t n = 0is huge in C++. Writei + 1 < n. - Early exit placed wrongly.
swappedmust be reset at the start of each pass and checked at its end; anything else disables the exit or exits too soon. - Comparator inconsistencies. A comparator that is not a strict weak ordering — including one over floats containing
NaN, which compares false with everything — can make any sort return garbage. Filter or map NaNs first. - Subtraction comparators overflow.
x - yoverflows in Java or C++ near the integer limits and flips the sign. UseInteger.compareorx < y. - Assuming a library sort is stable.
std::sortis not; Go'ssort.Sliceis not (sort.SliceStableis). - Quadratic sorts on large inputs. At , insertion sort on random data does about shifts — tens of seconds in Python. Read the constraints first.
Variations
- Cocktail shaker sort alternates left-to-right and right-to-left bubble passes so small elements near the end ("turtles") move fast. Still on average.
- Comb sort — bubble sort with a gap that shrinks by about 1.3 each pass; Shell's idea applied to bubble sort. Much faster in practice, still quadratic in the worst case.
- Odd-even transposition sort — bubble sort that compares all (even, odd) pairs, then all (odd, even) pairs, in parallel: rounds on processors in a line. A standard first parallel sort.
- Gnome sort — insertion sort with a single index that steps back after each swap; a curiosity.
- Library sort (gapped insertion sort; Bender, Farach-Colton and Mosteiro, 2006) leaves gaps like books on a shelf so insertions move few elements: with high probability, at the cost of extra space.
- Cycle sort — follows the cycles of the permutation and writes each element once, to its final position.
- Insertion sort on a linked list — relinking instead of shifting; stable, extra space (LeetCode 147 below). Merge sort does better on lists.
- Pancake sorting — only prefix reversals allowed; the selection-sort skeleton needs at most flips. The exact worst case for pancakes is known only for small .
- Sorting networks — data-independent compare-exchange sequences; optimal networks are known only for small (Knuth Vol. 3 §5.3.4).
Practice ladder
Easy → hard. Descriptions are paraphrased; follow the links for exact statements. Some have constraints where a quadratic sort is too slow — spotting that is part of the exercise.
1. Helpful Maths (Codeforces 339A) — rearrange the terms of a short sum of 1s, 2s and 3s into non-decreasing order. Teaches that with three distinct values, counting beats comparing.
Hint
Extract the digits, sort them (or count the 1s, 2s and 3s), and join with +.
2. Height Checker (LeetCode 1051) — count the positions where an array differs from its sorted version. Teaches comparing against the sorted order as an oracle.
Hint
Sort a copy and count mismatched indices. Heights are small, so counting sort gives .
Solution
def height_checker(heights: list[int]) -> int:
expected = sorted(heights)
return sum(1 for h, e in zip(heights, expected) if h != e)
assert height_checker([1, 1, 4, 2, 1, 3]) == 3
assert height_checker([5, 1, 2, 3, 4]) == 5
assert height_checker([1, 2, 3, 4, 5]) == 0
print("ok")
time, space. Note the answer is not the minimum number of swaps — it counts misplaced positions.
3. Sort the People (LeetCode 2418) — reorder names by their (distinct) heights, tallest first. Teaches sorting one array by keys stored in another: sort indices, or sort pairs.
Hint
Sort the indices range(n) by -heights[i], then map to names. Or zip, sort descending by height, unzip.
4. Sort Colors (LeetCode 75) — sort an array of 0s, 1s and 2s in place in one pass. Teaches that with three keys an elementary sort is the wrong tool: the Dutch national flag partition from Two Pointers is .
Hint
Three pointers lo, mid, hi; invariant a[0..lo-1] = 0, a[lo..mid-1] = 1, a[hi+1..] = 2. Do not advance mid after swapping with hi.
5. Queue at the School (Codeforces 266B) — a queue of boys and girls; every second, each boy standing directly in front of a girl swaps with her simultaneously. Print the queue after seconds. Teaches simulating one bubble-like pass correctly: the swaps in one second must not cascade.
Hint
In each second scan left to right; when you see "BG" at positions i, i+1, swap and skip to i + 2 so the same boy is not moved twice.
Solution
def queue_after(s: str, t: int) -> str:
q = list(s)
for _ in range(t):
i = 0
while i < len(q) - 1:
if q[i] == "B" and q[i + 1] == "G":
q[i], q[i + 1] = q[i + 1], q[i]
i += 2 # simultaneous swaps: do not move this boy again
else:
i += 1
return "".join(q)
assert queue_after("BGGBG", 1) == "GBGGB"
assert queue_after("BGGBG", 2) == "GGBGB"
assert queue_after("GGGB", 1) == "GGGB"
print("ok")
time. Without the i += 2 skip the scan would carry one boy all the way back in a single second — the bubble-sort "rabbit" effect.
6. Insertion Sort List (LeetCode 147) — sort a singly linked list with insertion sort. Teaches insertion by relinking instead of shifting, and the dummy-head trick.
Hint
Keep a dummy head for the sorted list. For each node of the input, walk the sorted list from the dummy until the next node's value is greater, and splice the node in there. Optimisation: if the node is the last inserted one, start the walk from there.
Solution
class ListNode:
def __init__(self, val: int = 0, next: "ListNode | None" = None):
self.val, self.next = val, next
def insertion_sort_list(head: ListNode | None) -> ListNode | None:
dummy = ListNode(0)
cur = head
while cur:
nxt = cur.next
prev = dummy
while prev.next and prev.next.val <= cur.val: # <= keeps equal values in input order
prev = prev.next
cur.next = prev.next
prev.next = cur
cur = nxt
return dummy.next
def build(xs):
d = ListNode()
t = d
for x in xs:
t.next = ListNode(x)
t = t.next
return d.next
def to_list(h):
out = []
while h:
out.append(h.val)
h = h.next
return out
assert to_list(insertion_sort_list(build([4, 2, 1, 3]))) == [1, 2, 3, 4]
assert to_list(insertion_sort_list(build([-1, 5, 3, 4, 0]))) == [-1, 0, 3, 4, 5]
assert to_list(insertion_sort_list(build([]))) == []
assert to_list(insertion_sort_list(build([2, 2, 1]))) == [1, 2, 2]
print("ok")
comparisons in the worst case, extra space, zero element moves. The walk starts at the front (scanning elements the key), unlike the array version, which scans from the back; both are stable.
7. Relative Sort Array (LeetCode 1122) — order one array by the order of values given in a second array, with leftovers at the end ascending. Teaches custom keys: a key can be a tuple.
Hint
Map each value of arr2 to its index. Sort arr1 by (rank.get(x, len(arr2)), x).
8. Sort Array by Increasing Frequency (LeetCode 1636) — sort by how often each value occurs, ascending, breaking ties by value descending. Teaches composite keys and that "then by" is either a tuple key or two stable sorts.
Hint
Count frequencies, then sort by (freq[x], -x). Equivalent with stability: sort by value descending, then stable-sort by frequency.
Solution
from collections import Counter
def frequency_sort(nums: list[int]) -> list[int]:
freq = Counter(nums)
return sorted(nums, key=lambda x: (freq[x], -x))
def frequency_sort_two_passes(nums: list[int]) -> list[int]:
freq = Counter(nums)
by_value_desc = sorted(nums, reverse=True)
return sorted(by_value_desc, key=lambda x: freq[x]) # stable: keeps value-desc among ties
for f in (frequency_sort, frequency_sort_two_passes):
assert f([1, 1, 2, 2, 2, 3]) == [3, 1, 1, 2, 2, 2]
assert f([2, 3, 1, 3, 2]) == [1, 3, 3, 2, 2]
assert f([-1, 1, -6, 4, 5, -6, 1, 4, 1]) == [5, -1, 4, 4, -6, -6, 1, 1, 1]
print("ok")
. The two-pass version is the multi-key stable sort from the Mechanics section, written out.
9. Distinct Numbers (CSES 1621) — count the distinct values among up to integers. Teaches "sort, then compare neighbours" — and that an elementary sort at this size would be about operations.
Hint
Sort with the built-in sort, then count positions where a[i] != a[i-1]. A hash set also works.
10. Pancake Sorting (LeetCode 969) — sort a permutation using only prefix reversals, returning any sequence of at most flips. Teaches the selection-sort skeleton under a restricted move set.
Hint
For size : find where value is, flip it to the front, then flip the first elements to send it to position . At most two flips per value.
Solution
def pancake_sort(arr: list[int]) -> list[int]:
a = list(arr)
flips = []
for size in range(len(a), 1, -1):
i = a.index(size) # values are a permutation of 1..n
if i == size - 1:
continue # already in place
if i != 0:
flips.append(i + 1)
a[:i + 1] = reversed(a[:i + 1])
flips.append(size)
a[:size] = reversed(a[:size])
return flips
def apply(arr, flips):
a = list(arr)
for k in flips:
a[:k] = reversed(a[:k])
return a
for arr in ([3, 2, 4, 1], [1, 2, 3], [2, 1], [5, 4, 3, 2, 1], [1, 5, 4, 3, 2]):
fl = pancake_sort(arr)
assert apply(arr, fl) == sorted(arr) and len(fl) <= 2 * len(arr)
print("ok")
time, at most flips. Selection sort's invariant ("the suffix holds the largest elements in order") with the swap replaced by two reversals.
11. Global and Local Inversions (LeetCode 775) — given a permutation of , decide whether its number of inversions equals its number of adjacent inversions. Teaches thinking in inversions instead of counting them.
Hint
Every adjacent inversion is also an inversion, so the counts are equal exactly when there is no inversion between elements two or more apart. For a permutation of that holds if and only if every value is within one position of its index.
Solution
def is_ideal_permutation(nums: list[int]) -> bool:
return all(abs(v - i) <= 1 for i, v in enumerate(nums))
def brute(nums):
n = len(nums)
glob = sum(1 for i in range(n) for j in range(i + 1, n) if nums[i] > nums[j])
loc = sum(1 for i in range(n - 1) if nums[i] > nums[i + 1])
return glob == loc
import itertools
assert is_ideal_permutation([1, 0, 2]) is True
assert is_ideal_permutation([1, 2, 0]) is False
for n in range(1, 7):
for p in itertools.permutations(range(n)):
assert is_ideal_permutation(list(p)) == brute(list(p))
print("ok")
time. Why: if value sits at index , positions hold values of which at most are smaller than , so at least two are larger, and one of them is not adjacent to — a non-local inversion. The case is symmetric. Conversely, if every value is within one of its index, every inversion is between neighbours. The exhaustive check up to confirms it.
12. Collecting Numbers (CSES 2216) — an array holds a permutation of ; you sweep left to right repeatedly, each time collecting the next numbers in increasing order as you meet them. How many sweeps? Teaches thinking in positions of values (the inverse permutation).
Hint
Let pos[v] be the index of value v. A new round starts each time pos[v+1] < pos[v]. The answer is 1 plus the number of such v.
13. Minimum Swaps to Arrange a Binary Grid (LeetCode 1536) — swap adjacent rows of an 0/1 grid so that every cell above the main diagonal is 0; minimise swaps. Teaches a greedy bubble-up: adjacent swaps, so the cost of moving a row up is the distance it travels.
Hint
Reduce each row to its number of trailing zeros. Row needs at least . For , find the first row at or below that qualifies and bubble it up to , adding the distance. If none qualifies, return . Taking the first qualifying row is safe: the rows it jumps over are all weaker.
14. Minimum Number of Moves to Make Palindrome (LeetCode 2193) — a string that can be rearranged into a palindrome; one move swaps two adjacent characters; find the minimum moves. Teaches adjacent-swap distance with a greedy that pairs from the outside in.
Hint
Look at the leftmost character. Find its matching occurrence closest to the right end and bubble it to the right end, counting the swaps; then strip both ends and repeat. If the leftmost character is the unpaired middle one, add its distance to the centre and drop it.
Solution
def min_moves_to_make_palindrome(s: str) -> int:
a = list(s)
moves = 0
while len(a) > 1:
j = len(a) - 1 - a[::-1].index(a[0]) # rightmost match of a[0]
if j == 0: # a[0] is the odd middle character
moves += len(a) // 2 # its distance to the centre
a.pop(0)
else:
moves += len(a) - 1 - j # bubble a[j] to the right end
a.pop(j)
a.pop(0)
return moves
assert min_moves_to_make_palindrome("aabb") == 2
assert min_moves_to_make_palindrome("letelt") == 2
assert min_moves_to_make_palindrome("abcba") == 0
assert min_moves_to_make_palindrome("ab" "ba") == 0
print("ok")
time, fine for the problem's limit of a few thousand characters. Counting the middle character's distance to the centre when it reaches the front gives the same total as moving it step by step (checked against breadth-first search on all arrangements of several small multisets). Optimality is an exchange argument: placing the outer pair first never increases the inversions left inside.
Common mistakes & interview follow-ups
"Which elementary sort would you actually use, and when?" Insertion sort, for small or nearly sorted arrays: stable, in place, adaptive, smallest constant factor. Selection sort only when writes dominate. Bubble sort never.
"What is the minimum number of adjacent swaps to sort this array?" The number of inversions, by the corollary above: each adjacent swap removes at most one, and bubble sort achieves exactly . Count it in with merge sort or a Fenwick tree, not by simulating.
"What is the minimum number of arbitrary swaps (any two positions)?" Different question: where is the number of cycles of the permutation (for distinct values). A swap raises the cycle count by at most one; putting an element in its place raises it by exactly one, which is what selection sort does.
"Is insertion sort stable? Prove it." Yes, because the inner loop moves elements strictly greater than the key; an equal element stops the loop, so the key ends up after it. The >= bug breaks it.
"The data arrives one element at a time." Insertion into a sorted array is per element. For large streams use a balanced BST ( per insert, Module 3) or, for the smallest only, a heap of size .
"Every element is at most positions from where it belongs." Insertion sort is . A min-heap of size gives : the smallest element in the window a[i..i+k] must be the next output.
"Why does Timsort use binary insertion sort but introsort plain insertion sort?" In Python comparisons are expensive dynamic calls and moves are pointer copies, so saving comparisons wins. C++ compares with an inlined, cheap operator<, where binary search's unpredictable branches cost more than they save.
"What if your comparator is inconsistent?" Java's Timsort may throw Comparison method violates its general contract!; in C++ it is undefined behaviour.
Quick quiz
1. How many shifts does insertion sort perform on [3, 1, 2], and how many comparisons?
Answer
Inversions: and , so 2 shifts. Comparisons: , since 1 is a new left-to-right minimum (it travels to index 0 and its loop ends on the bounds check). By hand: key 1 — compare with 3, shift, reach the front (1 comparison); key 2 — compare with 3, shift; compare with 1, stop (2 comparisons).
2. Bubble sort with early exit on [2, 3, 4, 5, 1]: how many passes and comparisons? What does insertion sort do on the same input?
Answer
The 1 moves left one position per pass, so bubble sort needs 4 passes with swaps; the fourth pass leaves the array sorted but there is no fifth pass to run for (passes are ). Comparisons: — the worst case, although . Insertion sort: keys 3, 4, 5 cost one comparison each, key 1 shifts four elements and reaches the front with 4 comparisons: 7 comparisons, 4 shifts.
3. Why is selection sort unstable even though it only ever picks the leftmost minimum?
Answer
Instability comes from the swap, not the choice. Swapping the minimum into position sends the element previously at to wherever the minimum was, possibly jumping over an element equal to it. Example: [(4,a), (2,b), (4,c), (1,d)] ends with (4,c) before (4,a).
4. You must sort by city ascending and, within a city, by age descending, using only a stable sort that takes a single key. In which order do you run the sorts?
Answer
Secondary key first: stable-sort by age descending, then stable-sort by city ascending. The second sort preserves the age order among people in the same city. (Or use one sort with the tuple key (city, -age).)
5. Shell sort's final pass is a plain insertion sort. Why is Shell sort faster than insertion sort, then?
Answer
Earlier passes with large gaps move elements many positions per shift, removing many inversions per move, and an -sorted array stays -sorted after later passes. By the final pass the array has few inversions, and insertion sort is , so the last pass is cheap.
Further reading / sources
- Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. (1998) — §5.1.1 (inversions), §5.2.1 (insertion sort, Shell sort, Theorem K), §5.2.2 (bubble sort, average passes), §5.2.3 (selection sort), §5.3.4 (sorting networks).
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — §2.1 (insertion sort and loop invariants), §2.2 (analysis), Problem 2-4 (inversions), Problem 2-2 (bubble sort).
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed. — §2.1 (elementary sorts, Shell sort, the sentinel exercise).
- Steven S. Skiena, The Algorithm Design Manual, 3rd ed. — §4.1–4.3 (applications of sorting, stability).
- Donald L. Shell, "A High-Speed Sorting Procedure", Communications of the ACM 2(7), 1959.
- Robert Sedgewick, "A New Upper Bound for Shellsort", Journal of Algorithms 7(2), 1986.
- Marcin Ciura, "Best Increments for the Average Case of Shellsort", Fundamentals of Computation Theory (FCT 2001), LNCS 2138.
- C. Greg Plaxton, Bjorn Poonen, Torsten Suel, "Improved Lower Bounds for Shellsort", FOCS 1992.
- Michael A. Bender, Martín Farach-Colton, Miguel A. Mosteiro, "Insertion Sort is ", Theory of Computing Systems 39(3), 2006 — library sort.
- Tim Peters, listsort.txt in the CPython source — Timsort's design,
minrun, and why binary insertion sort. - Orson Peters, "Pattern-defeating Quicksort" (arXiv:2106.05123) — partial insertion sort and the small-partition cutoff.
- cppreference:
std::sort,std::stable_sort— complexity and stability guarantees.
Lessons: previous — Sorting & Searching (overview) · next — Merge Sort & Inversion Counting · module — Searching & Sorting · course — DSA: Zero to Mastery.
Related Archon pages: Two Pointers · Linked Lists · Complexity Analysis · How Data Structures Live in Memory · Testing & Debugging Algorithms · Non-Comparison Sorts · Sorting in the Real World · Python cheat sheet.