
Merge sort sorts a list by splitting it in half, again and again, until every piece holds one item, which is already sorted. Then it merges the pieces back, always taking the smaller front item. For n items there are about log₂ n levels of merging, each costing at most n comparisons, so merge sort is O(n log n).
In this post we start with a 1930s machine that merged punched cards for US Social Security. Then we split eight numbers down to single cards, merge two sorted piles by hand, and write merge sort in Python. We count every comparison, for eight numbers and for a million. We see what a stable sort is, why Python's own sort is built on merging, and how merge sort looks in JavaScript.
A few words first. An algorithm is a list of steps that solves a problem. A comparison is one check of two items, such as "is 4 smaller than 2?". Sorting algorithms are measured by how many comparisons they make, because that's the work that grows fastest as the list gets longer.
Key takeaways
- Split: halve the list until every piece has one item. A one-item list is already sorted. Eight items take 3 rounds of halving; a million take 20, because 220 = 1,048,576.
- Merge: to join two sorted lists, compare only their two front items and take the smaller. Merging n items never takes more than n − 1 comparisons.
- Count: each level of merging costs at most n comparisons, and there are log₂ n levels, so merge sort is O(n log n). Insertion sort is O(n²).
- For a million shuffled numbers, our merge sort made 18,673,834 comparisons. Insertion sort makes about 250 billion on average: over 13,000 times more.
- Merge sort is stable: equal items keep their order, because
<=takes the left one on a tie. - Python's built-in sort, Timsort, is a mix of merge sort and insertion sort. Java uses a version of it to sort objects.
This post goes with letsBug Code, episode 8. Watch it first, or read on: everything in the video is here, plus every code sample with its real output, and practice questions with answers.
What problem does merge sort solve?
Sorting a big pile fast. In August 1935 President Franklin D. Roosevelt signed the law that set up Social Security, a scheme that pays people money when they retire. IBM's history page says "The challenge of creating and managing more than 27 million individual accounts had yet to be addressed." It also says "The law dictated that it be in place by January 1, 1937." Every account was kept on punched cards: paper cards that store data as a pattern of holes.
IBM built a machine for the job, the 077 collator (a machine that puts cards together in order). IBM says the 077 "was developed specifically for the SSA to sort tabulated cards". (The SSA is the Social Security Administration.) It was "capable of comparing, deduplicating and merging 240 to 480 paired cards per minute into a single pile." Deduplicating means removing copies. Workers put two piles of cards in. The machine "then merged the groups in numerical or alphabetical sequence." H. J. MacDonald, who led IBM's sales for the Social Security job, explained why they never tried to sort all the cards in one go: "To try to sort them together would have been out of the question as there were millions and millions."
That's the big idea of this post. Merging two piles that are already in order is easy. Sorting one shuffled pile is the hard part. So merge sort turns sorting into lots of merging.
Why sort at all? A sorted list lets you find things fast. Binary search finds an item in a sorted list of a million in at most 20 steps, by halving, just like merge sort's splits.
First, the slow way. Most people sort a hand of cards with insertion sort: take the next card and slide it left past every bigger one. The bubble sort and insertion sort post traces it step by step. On a shuffled pile, each new card slides past about half of the cards already sorted. That adds up to about n × (n − 1) / 4 comparisons for n cards, plus a few more for the comparisons that stop each slide. Those extra ones barely matter for a big pile. For a million cards that's 249,999,750,000, about 250 billion. That's O(n²): double the pile, and the work goes up four times.
Splitting a pile into more and more piles sounds like more work, not less. Let's count and see.
How does merge sort split a list?
In half, then in half again, until every piece has one item. Here are eight numbers: 38, 27, 43, 3, 9, 82, 10, 15. Split them in half: 38 27 43 3 and 9 82 10 15. Split each half again: four pairs. Split again: eight single numbers.
A list of one item is already sorted, because there's nothing to compare it with. Splitting does nothing else, and it costs no comparisons at all.
Eight items take 3 rounds of halving: 8, 4, 2, 1. How many rounds for a million? Halve 1,000,000 again and again, and you need 20 rounds to reach 1. Check it with powers of two: 219 = 524,288 is too small, and 220 = 1,048,576 is big enough. The number of halvings is written log₂ n (say "log base 2 of n"). It asks: how many times can you halve n until you reach 1? So log₂ 8 = 3, and log₂ 1,000,000 is just under 20. You can't do part of a halving, so round up: 20 levels.

How do you merge two sorted lists?
Look only at the two front items, and take the smaller one. Here are two sorted piles: 1, 4, 7, 10 and 2, 3, 8, 12.
| Fronts | Out goes | Merged | Count |
|---|---|---|---|
| 1 or 2 | 1 | 1 | 1 |
| 4 or 2 | 2 | 1, 2 | 2 |
| 4 or 3 | 3 | 1, 2, 3 | 3 |
| 4 or 8 | 4 | 1, 2, 3, 4 | 4 |
| 7 or 8 | 7 | 1, 2, 3, 4, 7 | 5 |
| 10 or 8 | 8 | 1, 2, 3, 4, 7, 8 | 6 |
| 10 or 12 | 10 | 1, 2, 3, 4, 7, 8, 10 | 7 |
| first pile is empty | 12, no comparison | 1, 2, 3, 4, 7, 8, 10, 12 | 7 |
Eight cards, 7 comparisons. Every comparison sends one card out. When one pile runs out, the rest of the other pile goes on the end with no comparisons at all. So merging n cards never takes more than n − 1 comparisons.

In Python, merge keeps two "fingers", i and j. Each one is an index, a position in a list, starting at the front of its pile:
def merge(left, right):
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
print(merge([1, 4, 7, 10], [2, 3, 8, 12]))
[1, 2, 3, 4, 7, 8, 10, 12]
While both piles still have items, the while loop compares the two fronts and appends the smaller. When one pile runs out, extend adds whatever is left of both. One of them is empty by then, so only the other one adds anything. left[i:] is a slice: every item from position i to the end.
How do you write merge sort in Python?
With seven lines that use merge from above:
def merge_sort(items):
if len(items) <= 1:
return items
mid = len(items) // 2
left = merge_sort(items[:mid])
right = merge_sort(items[mid:])
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10, 15]))
[3, 9, 10, 15, 27, 38, 43, 82]
Line by line:
- A list of one item, or none, is already sorted, so return it as it is. This is the base case: the point where the splitting stops.
- Otherwise, find the middle.
//divides and drops any remainder, so 8 // 2 is 4 and 7 // 2 is 3. - Merge sort the left half, then merge sort the right half.
- Merge the two sorted halves, and return the result.
Did you spot it? merge_sort calls itself, on smaller and smaller halves. A function that calls itself is called recursive, and the idea is called recursion. It works because every call gets a shorter list, so the calls always reach the base case. Merge sort is also called a divide-and-conquer algorithm: it divides the problem into smaller copies of itself, solves those, and joins the answers. Wikipedia says "Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945."
This merge_sort returns a new list and leaves the original alone, like Python's sorted(). The slices items[:mid] and items[mid:] are new lists, so nothing is shared. (Why that matters was the topic of the Python aliasing post.)
Why is merge sort O(n log n)?
Because it does at most n comparisons on each of about log₂ n levels. Picture the merges as levels, like in the diagram above. On one level, the merges together handle every card once. Each merge of k cards costs at most k − 1 comparisons, so a whole level costs at most n. The number of levels is log₂ n, the number of halvings. So the total is at most n × log₂ n.
For our eight cards: 3 levels × 8 cards = at most 24 comparisons. The diagram shows the real count: 4 + 6 + 7 = 17. For a million cards: 20 levels × 1,000,000 cards = at most 20,000,000.
You don't have to trust the sums. Let Python count. This version of merge adds 1 to count every time it compares two items. global count lets the function change the count that lives outside it. merge_sort stays the same, and it uses the new merge:
import random
count = 0
def merge(left, right):
global count
out = []
i = j = 0
while i < len(left) and j < len(right):
count += 1 # one comparison, on the next line
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
count = 0
merge_sort([38, 27, 43, 3, 9, 82, 10, 15])
print(count)
cards = random.Random(1).sample(range(10**8), 1_000_000)
count = 0
merge_sort(cards)
print(f"{count:,}")
17
18,673,834
random.Random(1).sample(range(10**8), 1_000_000) picks a million different numbers below 100 million, in a shuffled order. The 1 is a seed: it makes the "random" shuffle the same every time, so you can get our exact count. (A different shuffle gives a slightly different count, still under 20 million.) An f-string is a string starting with f that fills in values from your code, and the :, in it puts commas in the big number.
So a million cards: 18,673,834 comparisons with merge sort, against about 250 billion on average with insertion sort. That's over 13,000 times fewer comparisons. That's the difference between O(n log n) and O(n²). Wikipedia says "In sorting n objects, merge sort has an average and worst-case performance of O(n log n) comparisons." The Big O notation post explains what O(n log n) and O(n²) mean, by counting steps the same way.
| Cards | Merge sort, at most | Merge sort, counted | Insertion sort |
|---|---|---|---|
| 8 | 8 × 3 = 24 | 17 | 20 |
| 1,000,000 | 1,000,000 × 20 = 20,000,000 | 18,673,834 | 249,999,750,000 |
The merge sort limit is n × levels. The insertion sort number is counted for 8 cards, and about n(n − 1)/4, the average, for a million. Look at the first row. For 8 cards the counts are close: 17 for merge sort, 20 for insertion sort (counted with the code from the insertion sort post). On tiny lists, insertion sort is often faster anyway, because each step is simpler: it moves items inside one list, while merge sort makes new lists and calls itself again and again. So Python's own sort uses insertion sort for short pieces, as we'll see below. As n grows, merge sort pulls far ahead.
What is a stable sort, and why does it matter?
A stable sort keeps equal items in the order they started in. Merge sort is stable because of one character: the = in left[i] <= right[j]. When the two fronts are equal, it takes the left one first. The left pile came from earlier in the list, so equal items never swap places. If you wrote < instead, a tie would send the right one first, and the sort would stop being stable.
Why care? Say a teacher has a class register in name order and sorts it by grade. With a stable sort, students with the same grade stay in name order:
register = [("Ava", 7), ("Ben", 9), ("Cal", 7), ("Dev", 9)]
by_grade = sorted(register, key=lambda s: s[1])
print(by_grade)
[('Ava', 7), ('Cal', 7), ('Ben', 9), ('Dev', 9)]
Each student is a tuple, a pair of values in round brackets. key=lambda s: s[1] tells sorted to compare only the grade, the second item of each tuple. (A lambda is a tiny function with no name.) Ava and Cal both have 7, and Ava stays first, just as in the register. Python's docs promise this: "Sorts are guaranteed to be stable. That means that when multiple records have the same key, their original order is preserved."
What sorting algorithm does Python use?
Python's built-in sort is built on merging, too. It's called Timsort, and Tim Peters wrote it for Python. Wikipedia describes Timsort as "a tuned hybrid of merge sort and insertion sort" (a hybrid is a mix of two things), and says it "is used by Python since version 2.3". Tim Peters's own notes, kept with Python's source code, open with: "This describes an adaptive, stable, natural mergesort, modestly called timsort". (Natural means it uses the runs already in the list. "Modestly" is a joke: he named it after himself.) Adaptive means it does less work on lists that are already partly in order. The notes say it walks the list once, "alternately identifying the next run, then merging it into the previous runs". A run is a stretch of the list that is already in order. Short runs are made longer with insertion sort, and a list with fewer than 64 items is sorted with insertion sort alone. Python's docs sum it up: "The Timsort algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset." (Since Python 3.11, the rule for which runs to merge first comes from a newer method called Powersort.)
Java uses the same idea. Oracle's documentation for Java's Arrays.sort on objects says it is "a stable, adaptive, iterative mergesort", and that it "was adapted from Tim Peters's list sort for Python". (Iterative means it uses loops instead of calling itself.) For arrays of basic number types, like int and double, Java uses a different algorithm, a Dual-Pivot Quicksort.
How do you write merge sort in JavaScript?
The same way: a merge that compares fronts, and a mergeSort that splits and calls itself.
function merge(left, right) {
const out = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) out.push(left[i++]);
else out.push(right[j++]);
}
return out.concat(left.slice(i), right.slice(j));
}
function mergeSort(items) {
if (items.length <= 1) return items;
const mid = Math.floor(items.length / 2);
return merge(mergeSort(items.slice(0, mid)), mergeSort(items.slice(mid)));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10, 15]).join(", "));
3, 9, 10, 15, 27, 38, 43, 82
left[i++] uses the item at i, then adds 1 to i. Math.floor rounds down, like Python's //. concat joins the leftovers on the end, like extend.
In real JavaScript code you'd use the built-in sort, but watch out with numbers:
console.log([10, 9, 82].sort().join(", "));
console.log([10, 9, 82].sort((a, b) => a - b).join(", "));
10, 82, 9
9, 10, 82
The first line sorts the numbers as text. MDN, the reference site for web developers, says: "The default sort order is ascending, built upon converting the elements into strings, then comparing their sequences of UTF-16 code unit values." (A code unit is the number the computer stores for each character.) As text, "10" comes before "82", and "82" before "9", just like words in a dictionary. The fix is a compare function, (a, b) => a - b, which tells sort to compare the numbers as numbers. And like Python's, JavaScript's sort is stable. ECMAScript is the official name of the JavaScript standard, and MDN says "Since version 10 (or ECMAScript 2019), the specification dictates that Array.prototype.sort is stable."
Is merge sort on the GCSE Computer Science course?
It is on OCR's. OCR's GCSE Computer Science specification (J277) lists three standard sorting algorithms: bubble sort, merge sort and insertion sort. You need to "Understand the main steps of the algorithm" and "Apply the algorithm to a data set". You don't need "To remember the code, pseudocode or Exam Reference Language" for it. (Pseudocode is code-like steps written in plain English. Exam Reference Language is OCR's own version of it.) So in an exam, be ready to draw the split-and-merge diagram for a short list, like the one above, and to say which algorithm a piece of code is. Other exam boards have their own specifications, so check the one for your course.
Two short sentences cover the main steps. One: split the list in half repeatedly until each sublist (smaller list) has one item. Two: merge pairs of sublists back together, comparing the front items and taking the smaller, until one sorted list is left.
Does assigning to [[]] * 4 change every list?
That was last week's challenge: episode 7 ended with this puzzle. Four players share one inventory list, made with inventories = [[]] * 4. Instead of appending, we write inventories[0] = ["sword"]. Does every player get a sword?
inventories = [[]] * 4
inventories[0] = ["sword"]
print(inventories)
[['sword'], [], [], []]
No. Assignment doesn't change the shared list. It ties slot 0 to a brand-new list. The other three slots still point to the one shared empty list, so only player one has a sword. Appending changes the object; assigning moves a name tag. The Python aliasing post explains name tags and shared lists in full.
1) Two classes sat the same test. Each teacher's list of scores is already sorted. Class A: 52, 67, 81, 90. Class B: 45, 70, 88. Merge them into one list. How many comparisons does it take?
2) How many levels of splitting does merge sort need for 1,000,000 items? And at most how many comparisons?
3) Draw merge sort on 5, 2, 4, 1. How many comparisons does it make?
4) The video's challenge: in merge_sort, change mid = len(items) // 2 to mid = 1, so each split peels off just one item. Does it still sort the eight numbers? What happens with a thousand?
Show the answers
1) 6 comparisons: 45, 52, 67, 70, 81, 88, and when class B runs out, 90 goes on the end with no comparison. Seven scores, six comparisons, which is n − 1.
2) 20 levels, because 220 = 1,048,576 is the first power of two that reaches a million. So at most 20 × 1,000,000 = 20,000,000 comparisons. Our count was 18,673,834.
3) Split into 5, 2 and 4, 1, then into single items. Merge 5 and 2 into 2, 5 (1 comparison). Merge 4 and 1 into 1, 4 (1 comparison). Merge 2, 5 and 1, 4: 2 or 1? 1. 2 or 4? 2. 5 or 4? 4. Then 5 goes on the end (3 comparisons). Result 1, 2, 4, 5 in 5 comparisons.
4) The eight numbers still come out sorted, but in 21 comparisons instead of 17, because the splits are lopsided. With a thousand items it crashes with a RecursionError. Each call peels off one item and calls itself on the rest, so the calls nest about a thousand deep before any of them finishes. Python stops at its recursion limit, which is 1,000 by default, so a thousand items is just past it (check yours with sys.getrecursionlimit()). Python's docs say the limit is "the maximum depth of the Python interpreter stack". The stack is Python's pile of function calls that haven't finished yet. The docs add: "This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python." In other words, the limit stops a runaway function from crashing Python itself. Halving in the middle keeps the calls only about 20 deep, even for a million items.
Questions people ask
What is the time complexity of merge sort?
O(n log n) in the best, average and worst case. The version in this post always splits all the way down and merges everything back, even when the list is already sorted. On a sorted million it still counted 9,884,992 comparisons. Insertion sort needs just 999,999 on a sorted list, one per card after the first. That's why Python's Timsort looks for runs that are already in order first.
Is merge sort stable?
Yes, as long as the merge takes the left item on a tie, which <= does. Wikipedia says "Most implementations of merge sort are stable, which means that the relative order of equal elements is the same between the input and output." Python's sorted() and list.sort() are guaranteed stable too.
Is merge sort better than quicksort?
Each wins somewhere. Quicksort is another divide-and-conquer sort. It picks one item, the pivot, puts smaller items on one side and bigger items on the other, then sorts each side the same way. Wikipedia says that in the worst case, with unlucky pivots, quicksort makes O(n²) comparisons. Merge sort is stable and always O(n log n). Wikipedia says "In the worst case, merge sort uses approximately 39% fewer comparisons than quicksort does in its average case". But merge sort needs extra memory: about n extra slots for the merged lists, which is O(n) space (the extra memory grows in step with n). Quicksort needs only O(log n) extra space, and Wikipedia says that helps it use the computer's cache (its small, fast memory) better. Wikipedia adds that "Merge sort is often the best choice for sorting a linked list". A linked list is a list where each item only knows where the next one is, so you can't jump straight to the middle.
Does Python use merge sort?
Python uses Timsort, which is a hybrid of merge sort and insertion sort. It finds stretches of the list that are already in order, sorts short pieces with insertion sort, and merges the pieces. Use sorted(items) or items.sort() in real code. Write your own merge sort only to learn how it works.
Who invented merge sort?
John von Neumann, in 1945, according to Wikipedia. The idea of merging sorted piles is older: IBM's 077 collator was already merging punched cards for US Social Security in the 1930s.
What is the base case in merge sort?
A list with one item or none: if len(items) <= 1: return items. It's already sorted, so the function returns it without calling itself again. Every recursive function needs a base case, or the calls never stop.
Keep going
- Watch the full lesson, Merge Sort in Python, Explained: Sort a Million Cards by Splitting in Half, and its Short, How Does Merge Sort Work? Split the Pile in Half, Again and Again. There's also a Short on merging two sorted lists, one comparison at a time. More in the letsBug Code series on YouTube. Next in the series: two pointers, finding a pair that sums to a target without checking every pair.
- The episode before this one: Python aliasing: why changing b also changes a.
- The slow sorts that merge sort beats, traced by hand: bubble sort and insertion sort in Python. And why counting steps matters: Big O notation in Python.
Checked on 15 November 2026 against the 10 sources below.
Sources
- IBM History: The IBM 077 Collator (Social Security dates, 27 million accounts, merging 240 to 480 cards a minute)
- Wikipedia: Merge sort (von Neumann 1945, O(n log n), stability, vs quicksort, Timsort in Python since 2.3 and Powersort since 3.11)
- Python documentation: Sorting Techniques (sorts are guaranteed stable; Timsort)
- CPython source: Objects/listsort.txt, Tim Peters's notes on Timsort (runs, insertion sort under 64 items, Powersort)
- Wikipedia: Quicksort (pivots, O(n²) worst case)
- Oracle, Java SE 21 API: java.util.Arrays (object sort is a mergesort adapted from Python's Timsort; Dual-Pivot Quicksort for numbers)
- Python documentation: sys.getrecursionlimit() (the recursion limit)
- Python documentation: RecursionError (raised when the limit is passed)
- MDN Web Docs: Array.prototype.sort() (default sort compares as strings; stable since ES2019)
- OCR: GCSE Computer Science J277 specification, version 3.1, section 2.1.3 (bubble, merge and insertion sort)
Every code sample in this post was run in Python 3.13.2 and Node.js 24 before publishing, and every output shown is the real output.