No Sorting Algorithm Wins. Look at Your Data First.
Ask which sorting algorithm is fastest and you get a ranking: quicksort, then merge sort, then the quadratic ones you should not use. The ranking is not wrong so much as unanswerable as asked, because it describes the algorithms and says nothing about the input — and the input decides.
Across five shapes of the same 64 values, four different algorithms take the cheapest slot.
Predict, then look
The costs stay hidden until you commit.
The summary most people carry — quicksort is fast, insertion sort is slow, merge sort is O(n log n) — describes the algorithms without describing the input, which is the half that decides the answer. Across 5 shapes of 64-element input, counting one unit per comparison and one per element moved, 3 different algorithms take the cheapest slot.
Insertion sort wins on already-sorted input at 189 units, where merge sort needs 960 and it is not close. Merge sort wins on reversed input. Quicksort with a naive first-element pivot wins on scrambled input at 765 — and is the worst of the four on already-sorted input at 2142, which is 2.8× its own cost on scrambled data.
That last failure is the one to carry away, because this cluster has shown it before: a naive pivot on sorted input partitions into one empty side and one side holding everything, which is exactly what inserting sorted keys into a binary search tree does. Sorted input is the pathological case, and sorted is the order data most often arrives in.
Choose a shape of input, then predict which algorithm does the least work on it. The costs stay hidden until you commit. Try all five — one favourite will not carry you.
Your prediction
- Score
- 0/0
- Distinct winners seen
- 0
- Cheapest here
- ?
- Dearest here
- ?
The same round, as values
Input
Total work
Split
Try all five shapes. If you pick the same algorithm every time, you will score about one in four.
One unit is one comparison or one element moved. Counting both is deliberate: comparisons alone flatter merge sort, which compares little and copies constantly, and moves alone flatter it the other way.
The results, and what each one means
def insertion(data):
a, comps, moves = list(data), 0, 0
for i in range(1, len(a)):
key, j = a[i], i - 1
moves += 1
while j >= 0:
comps += 1
if a[j] > key:
a[j + 1] = a[j]
moves += 1
j -= 1
else:
break
a[j + 1] = key
moves += 1
return a, comps, moves
def merge_sort(data):
a, stats = list(data), [0, 0] # comps, moves
def sort(lo, hi):
if hi - lo <= 1:
return
mid = (lo + hi) // 2
sort(lo, mid)
sort(mid, hi)
left, right = a[lo:mid], a[mid:hi]
stats[1] += len(left) + len(right) # copied out
i = j = 0
k = lo
while i < len(left) and j < len(right):
stats[0] += 1
if left[i] <= right[j]:
a[k] = left[i]
i += 1
else:
a[k] = right[j]
j += 1
stats[1] += 1
k += 1
while i < len(left):
a[k] = left[i]
i += 1
k += 1
stats[1] += 1
while j < len(right):
a[k] = right[j]
j += 1
k += 1
stats[1] += 1
sort(0, len(a))
return a, stats[0], stats[1]
def quicksort(data, pivot):
a, stats = list(data), [0, 0]
def sort(lo, hi):
if hi - lo <= 1:
return
if pivot == "median3":
mid = (lo + hi - 1) // 2
trio = sorted([(a[lo], lo), (a[mid], mid), (a[hi - 1], hi - 1)])
p = trio[1][1]
a[lo], a[p] = a[p], a[lo]
stats[1] += 2
stats[0] += 3 # the three comparisons that ordered the trio
value = a[lo]
i = lo + 1
for j in range(lo + 1, hi):
stats[0] += 1
if a[j] < value:
a[i], a[j] = a[j], a[i]
stats[1] += 2
i += 1
a[lo], a[i - 1] = a[i - 1], a[lo]
stats[1] += 2
sort(lo, i - 1)
sort(i, hi)
sort(0, len(a))
return a, stats[0], stats[1]
def shapes(n):
ordered = list(range(1, n + 1))
nearly = list(ordered)
for i in range(0, n - 1, max(1, n // 8)): # a few adjacent swaps
nearly[i], nearly[i + 1] = nearly[i + 1], nearly[i]
pseudo = [(i * 37 + 11) % n for i in range(n)] # deterministic scramble
return {
"already sorted": ordered,
"nearly sorted": nearly,
"reversed": ordered[::-1],
"scrambled": pseudo,
"many duplicates": [(i * 37) % 4 for i in range(n)],
}
N = 64
ALGOS = [
("insertion", lambda d: insertion(d)),
("merge", lambda d: merge_sort(d)),
("quick, first pivot", lambda d: quicksort(d, "first")),
("quick, median of 3", lambda d: quicksort(d, "median3")),
]
print(f"{'input shape':<16}" + "".join(f"{name:>21}" for name, _ in ALGOS))
print(f"{'':<16}" + "".join(f"{'comparisons + moves':>21}" for _ in ALGOS))
for shape, data in shapes(N).items():
cells = []
for name, fn in ALGOS:
out, comps, moves = fn(data)
assert out == sorted(data), f"{name} failed on {shape}"
cells.append(f"{comps + moves:>21,}")
print(f"{shape:<16}" + "".join(cells))
print()
print("Where does merge sort overtake insertion sort on scrambled input?")
print(f"{'n':>5} {'insertion':>11} {'merge':>9} cheaper")
for n in (8, 16, 32, 64, 128, 256):
data = shapes(n)["scrambled"]
_, ic, im = insertion(data)
_, mc, mm = merge_sort(data)
print(f"{n:>5} {ic + im:>11,} {mc + mm:>9,} {'insertion' if ic + im < mc + mm else 'merge'}")input shape insertion merge quick, first pivot quick, median of 3
comparisons + moves comparisons + moves comparisons + moves comparisons + moves
already sorted 189 960 2,142 746
nearly sorted 204 960 1,870 746
reversed 4,158 960 4,190 1,321
scrambled 2,177 1,085 765 875
many duplicates 1,629 1,056 860 1,188
Where does merge sort overtake insertion sort on scrambled input?
n insertion merge cheaper
8 42 64 insertion
16 178 174 merge
32 608 442 merge
64 2,177 1,085 merge
128 8,258 2,540 merge
256 32,449 5,798 merge The assert on every row is not decoration — a cheaper sort that did not sort would not be cheaper,
it would be broken, so each result is checked against Python’s own sorted.
Insertion sort is not slow. On already-sorted input it costs 189 units where merge sort costs 960, because it does one comparison per element and stops. Its reputation comes from one shape (reversed, 4,158) being taken as the whole story. Nearly-sorted data is extremely common — an append to a mostly-ordered file, a re-sort after a few edits — and insertion sort is close to unbeatable on it.
Quicksort with a naive pivot is both the best and the worst. 765 units on scrambled input, the cheapest anything scores anywhere in the table — and 2,142 on already-sorted input, the dearest. Same algorithm, same values, different order.
That failure should look familiar. Taking the first element as the pivot on sorted data partitions into an empty side and a side containing everything, which is precisely what inserting sorted keys into a binary search tree does to a tree. One structure and one algorithm, the same catastrophe, for the same reason.
Median-of-three costs a little and removes the catastrophe. 746 on sorted input against the naive version’s 2,142, for three extra comparisons per partition. It gives up a little on scrambled input (875 against 765) and never falls apart. That trade — slightly worse typical, dramatically better worst case — is what production sorts buy.
Why real sorts use more than one algorithm
The second table is the reason. On scrambled input insertion sort is cheaper than merge sort at n = 8 and loses from n = 16 — there is a crossover, and below it the “worse” algorithm is the better choice.
Real implementations exploit this. Python’s list.sort and Java’s Arrays.sort both run Timsort,
which finds already-ordered runs and uses insertion sort on short ones; C++‘s std::sort typically
runs introsort, which is quicksort that switches to insertion sort on small partitions and to heap
sort when recursion goes too deep. None of them picks an algorithm. They pick one per region of
the data, having looked at it.
What this page simplifies
- The crossover here is lower than in real code. This model does not charge for recursive calls or for allocating the merge buffers, and both run against merge sort — which is why real implementations switch to insertion sort at thresholds nearer 32 or 64 than 16.
- Units, not seconds. Comparisons and moves are deterministic and identical on any machine. Timings would additionally reflect cache behaviour, which favours the in-place sorts.
- One deterministic scramble. “Scrambled” is a fixed sequence, not an average over random inputs. Quicksort’s reputation rests on the average, and one sample is not an average.
- No stability, no memory. Merge sort is stable and needs O(n) extra space; quicksort is neither stable nor extra-hungry. For sorting records by one field of several, stability alone can decide the choice before any of these numbers matter.