Sorting Algorithms Compared
Why sorting matters, how insertion, merge and quick sort actually work, what stability means, and how to choose between them. Includes counted comparisons, so the costs are measured instead of memorised.
Why sorting is worth a whole lesson
Open any contacts app, a spreadsheet, a leaderboard or a file manager and you are looking at sorted data. Sorting is rarely the goal, though. It is the cheap preparation that makes the real question easy: once a list is ordered you can binary search it in logarithmic time, spot duplicates because equal values sit side by side, merge two lists in one pass, or find the median by looking in the middle.
That is why every standard library ships an excellent sort and why you will almost never write one in production. You study sorting for a different reason: it is the cleanest laboratory for the ideas that run through the rest of algorithms. Insertion sort shows what an invariant is. Merge sort shows divide and conquer. Quick sort shows how a clever choice of pivot trades worst-case safety for average-case speed. Comparing them teaches you to ask the right questions of any algorithm: how many steps, how much extra memory, and what guarantees survive bad input.
A sort is stable if records with equal keys keep the relative order they had in the input. Sorting people by city with a stable sort leaves each city's people in their previous (say, alphabetical) order.
Insertion sort: the way you sort playing cards
Pick up cards one at a time and slide each into its place among the cards already in your hand. That is insertion sort. The hand on the left is always sorted; the pile on the right is untouched; each step takes the next element and shifts larger elements one slot right until the gap fits it.
The invariant is the whole idea: after step i, the first i elements are sorted. It is true before the loop starts (one element is trivially sorted) and each iteration preserves it, so when the loop ends everything is sorted. Learning to state an invariant like this is more valuable than the algorithm itself, because it is how you prove any loop correct.
The cost depends on the input. On an already sorted list every element needs one comparison and no shifting, so the work is linear. On a reversed list every element travels all the way to the front, which is about n squared over two moves. For small lists, and for lists that are nearly sorted, insertion sort is genuinely hard to beat, which is why real library sorts finish with it.
sorted prefix | unsorted [ 2 5 9 ] 4 1 7 key = 4 [ 2 5 9 ] -> 9 > 4, shift [ 2 5 _ 9 ] [ 2 5 _ 9 ] -> 5 > 4, shift [ 2 _ 5 9 ] [ 2 _ 5 9 ] -> 2 < 4, stop [ 2 4 5 9 ] prefix is sorted again: [ 2 4 5 9 ] | 1 7
1def insertion_sort(items):2 items = list(items)3 comparisons = 04 for i in range(1, len(items)):5 key = items[i]6 j = i - 17 while j >= 0:8 comparisons += 19 if items[j] > key:10 items[j + 1] = items[j]11 j -= 112 else:13 break14 items[j + 1] = key15 return items, comparisons1617for name, data in [("sorted", [1, 2, 3, 4, 5, 6, 7, 8]),18 ("reversed", [8, 7, 6, 5, 4, 3, 2, 1]),19 ("mixed", [5, 2, 9, 4, 1, 7, 3, 8])]:20 result, count = insertion_sort(data)21 print(name, result, "comparisons:", count)
sorted [1, 2, 3, 4, 5, 6, 7, 8] comparisons: 7 reversed [1, 2, 3, 4, 5, 6, 7, 8] comparisons: 28 mixed [1, 2, 3, 4, 5, 7, 8, 9] comparisons: 18
Merge sort: divide, conquer, combine
Insertion sort does too much work because it moves elements one slot at a time. Merge sort starts from a different observation: merging two sorted lists is cheap. Walk a finger down each list, always copy the smaller front element, and in one pass over n elements you have a single sorted list.
If merging sorted halves is easy, sorting becomes a recursion. Split the list in half, sort each half the same way, and merge. A list of one element is already sorted, which is the base case. Nothing fancy happens at any level; the power comes from the depth. Halving n elements takes about log2 n levels, and every level does a total of n units of merging work, so the cost is n log n regardless of the input order.
There is a price. Merging needs somewhere to put the output, so the standard version uses O(n) extra memory. In exchange you get a worst case that never degrades and a naturally stable sort, as long as ties are taken from the left half first (the <= in the code below).
[5 2 9 4 1 7 3 8]
/ \
[5 2 9 4] [1 7 3 8]
/ \ / \
[5 2] [9 4] [1 7] [3 8]
/ \ / \ / \ / \
[5] [2] [9] [4] [1] [7] [3] [8]
\ / \ / \ / \ /
[2 5] [4 9] [1 7] [3 8]
\ / \ /
[2 4 5 9] [1 3 7 8]
\ /
[1 2 3 4 5 7 8 9]Compare the counts with insertion sort above. On the reversed list insertion sort pays for every inversion, while merge sort stays in a narrow band whatever the order. That predictability is exactly what you are buying with the extra memory.
1def merge_sort(items):2 if len(items) <= 1:3 return list(items), 04 mid = len(items) // 25 left, c1 = merge_sort(items[:mid])6 right, c2 = merge_sort(items[mid:])7 merged, i, j, c3 = [], 0, 0, 08 while i < len(left) and j < len(right):9 c3 += 110 if left[i] <= right[j]: # <= keeps equal keys in input order (stable)11 merged.append(left[i]); i += 112 else:13 merged.append(right[j]); j += 114 merged.extend(left[i:])15 merged.extend(right[j:])16 return merged, c1 + c2 + c31718for name, data in [("sorted", list(range(1, 9))),19 ("reversed", list(range(8, 0, -1))),20 ("mixed", [5, 2, 9, 4, 1, 7, 3, 8])]:21 result, count = merge_sort(data)22 print(name, result, "comparisons:", count)
sorted [1, 2, 3, 4, 5, 6, 7, 8] comparisons: 12 reversed [1, 2, 3, 4, 5, 6, 7, 8] comparisons: 12 mixed [1, 2, 3, 4, 5, 7, 8, 9] comparisons: 17
Quick sort: partition around a pivot
Quick sort divides differently. Instead of splitting by position and doing the work while merging, it does the work while splitting. Choose a pivot value, rearrange the list so everything smaller is on its left and everything larger on its right, and the pivot is now in its final position forever. Then sort the two sides independently. There is nothing to combine at the end.
When the pivot lands near the middle, the recursion is as balanced as merge sort and the total is n log n. The danger is a bad pivot. If you always take the first element and the list is already sorted, each partition peels off a single element, the recursion is n levels deep and the cost collapses to n squared. This is not a theoretical curiosity: a naive quick sort on sorted data is both slow and can overflow the call stack.
The standard defences are cheap. Pick the pivot at random, or use the median of the first, middle and last elements. With a random pivot the bad case needs a ridiculously unlucky sequence of choices, so the expected cost is n log n for every input. Because partitioning can be done by swapping inside the array, quick sort needs only O(log n) stack space on average, and it touches memory in a cache-friendly sequential pattern. That, rather than a better big-O, is why it is often fastest in practice.
The version above builds new lists for clarity. Production quick sorts partition in place; the idea and the pivot problem are identical.
1def quick_sort(items, pick):2 """Returns (sorted list, total comparisons). pick chooses the pivot."""3 if len(items) <= 1:4 return list(items), 05 pivot = pick(items)6 smaller = [x for x in items if x < pivot]7 equal = [x for x in items if x == pivot]8 larger = [x for x in items if x > pivot]9 left, c1 = quick_sort(smaller, pick)10 right, c2 = quick_sort(larger, pick)11 return left + equal + right, c1 + c2 + len(items)1213def first(items):14 return items[0]1516def median_of_three(items):17 a, b, c = items[0], items[len(items) // 2], items[-1]18 return sorted([a, b, c])[1]1920data = list(range(1, 201)) # already sorted: the classic trap21shuffled = [(i * 37) % 200 for i in range(200)]22for label, values in [("sorted input", data), ("scrambled input", shuffled)]:23 for name, pick in [("first", first), ("median-of-three", median_of_three)]:24 result, count = quick_sort(values, pick)25 assert result == sorted(values)26 print(label, "| pivot:", name, "| comparisons:", count)
sorted input | pivot: first | comparisons: 20099 sorted input | pivot: median-of-three | comparisons: 1280 scrambled input | pivot: first | comparisons: 1881 scrambled input | pivot: median-of-three | comparisons: 1330
Choosing between them
No single sort wins everywhere, which is why the decision is worth making deliberately. The table summarises what you have just seen. "Extra space" counts memory beyond the input itself.
Comparison sorts at a glance
| Algorithm | Best | Average | Worst | Extra space | Stable |
|---|---|---|---|---|---|
| Insertion sort | O(n) sorted input | O(n^2) | O(n^2) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort (random pivot) | O(n log n) | O(n log n) | O(n^2), vanishingly unlikely | O(log n) stack | No (in-place version) |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
There is a floor under all of this. Any algorithm that sorts only by comparing pairs of elements needs at least about n log n comparisons in the worst case, because n elements have n factorial orderings and each comparison can at best halve the possibilities. Faster sorts exist (counting sort, radix sort) but they cheat by exploiting the structure of the keys instead of only comparing them.
Stability in practice
Stability sounds like a footnote until you sort by more than one key. A spreadsheet user sorts a table by name, then by department, and expects people inside each department to remain alphabetical. That works only if the second sort is stable. Python's built-in sorted() and list.sort() use Timsort, which is stable, so multi-pass sorting is a reliable idiom: sort by the least important key first and the most important key last.
1staff = [("Maya", "ops"), ("Noor", "dev"), ("Ben", "ops"),2 ("Alice", "dev"), ("Zed", "ops"), ("Cara", "dev")]34by_name = sorted(staff, key=lambda p: p[0])5print("by name: ", [p[0] for p in by_name])67by_dept = sorted(by_name, key=lambda p: p[1])8print("then by dept: ", [(p[1], p[0]) for p in by_dept])910# One pass with a tuple key gives the same result without relying on stability11print("tuple key: ", sorted(staff, key=lambda p: (p[1], p[0])) == by_dept)
by name: ['Alice', 'Ben', 'Cara', 'Maya', 'Noor', 'Zed']
then by dept: [('dev', 'Alice'), ('dev', 'Cara'), ('dev', 'Noor'), ('ops', 'Ben'), ('ops', 'Maya'), ('ops', 'Zed')]
tuple key: TrueMisconceptions worth correcting
"Quick sort is always faster than merge sort." Not in the worst case, and not when you need stability or guaranteed latency. It is usually faster on arrays in memory; on linked lists, where random access is slow and merging needs no extra space, merge sort is the natural choice.
"Big-O says insertion sort is bad." Big-O describes growth. For a dozen elements, or a nearly sorted list, the tiny constant factor wins, and that is why hybrid sorts use it for small partitions.
"I should implement my own sort for speed." Almost never. The library version is tested, tuned and stable. Write your own to understand it, then call sorted() or Array.prototype.sort and spend your effort on the comparison key.
Forgetting the comparator for numbers in JavaScript. [10, 9, 1].sort() compares as strings and yields [1, 10, 9]. Pass (a, b) => a - b.
1const values = [10, 9, 1, 100];2console.log([...values].sort());3console.log([...values].sort((a, b) => a - b));
[ 1, 10, 100, 9 ] [ 1, 9, 10, 100 ]
Check your understanding
Answer these before moving on. Each one tests a reason, not a definition.
A list of 1,000 timestamps is almost sorted: only a handful of entries are slightly out of place. Which algorithm is likely to finish with the least work?
Quick Syntax & Reference Sheet
| Concept / Rule | Syntax / Usage |
|---|---|
| Insertion sort | Keep prefix sorted; shift larger items right; drop key in the gap. O(n^2), O(n) if nearly sorted, stable, O(1) space. |
| Merge sort | Split in half, sort each, merge with two fingers. O(n log n) always, stable, O(n) space. |
| Quick sort | Pick pivot, partition smaller | pivot | larger, recurse. O(n log n) expected, O(n^2) worst, not stable. |
| Python multi-key sort | sorted(rows, key=lambda r: (r.dept, r.name)) |
| JavaScript numeric sort | values.sort((a, b) => a - b) |
Common Pitfalls & Developer Mistakes
Using the first or last element as quick sort pivot on data that may already be sorted
Why it happens: Sorted and reverse-sorted inputs are common in the real world, and they produce maximally unbalanced partitions.
Sorting numbers in JavaScript without a comparator
Why it happens: Array.prototype.sort converts elements to strings by default, so 10 sorts before 9.
Merging with < instead of <= and then relying on stability
Why it happens: Taking from the right half on ties reverses the original order of equal keys.