Originally published on CodingCush.

Merge sort is a sorting algorithm that splits a list in half again and again until every piece has one value, then merges those tiny sorted pieces back together in order. It takes about the same amount of work no matter how shuffled the input is, which is why it is a favourite in interviews and in real code, including Python's own sorted(). In this guide you will dry run it by hand, write the complete Python version, and test its speed against sorted(). All outputs are from real runs on Python 3.12.3.

How Merge Sort Works, in Plain Words

Imagine sorting a messy pile of numbered cards with a friend helping. You split the pile in half, your friend splits their half in half, and so on, until everyone holds a single card. Then you pair up and merge your sorted piles: each pair compares the top card of each pile, takes the smaller one, and repeats until one neat pile is left.

That is the whole idea, and it has a proper name: divide and conquer. The divide step keeps halving the list until the pieces are too small to split. The conquer step merges two sorted lists by always picking the smaller front value. Merging two sorted lists is cheap, and that is the trick that makes the whole algorithm fast.

Two details matter. Merge sort is stable, because when the two front values are equal it takes the one from the left pile first, so equal values keep their original order. And it needs extra memory, because each merge builds a new list instead of shuffling values inside the original one.

A Dry Run on a Small List, Step by Step

Let us sort [38, 27, 43, 3, 9, 82, 10] by hand. First split it in half, then split the halves, until every piece holds one value:

[38, 27, 43, 3, 9, 82, 10] -> [38, 27, 43, 3] and [9, 82, 10] -> [38, 27] [43, 3] | [9, 82] [10] -> [38] [27] [43] [3] | [9] [82] [10] 

Now merge the pairs back. [38] and [27] become [27, 38], [43] and [3] become [3, 43], [9] and [82] become [9, 82], and [10] waits alone:

[27, 38] [3, 43] | [9, 82] [10] -> [3, 27, 38, 43] and [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82] 

Watch the last merge closely. Compare 3 and 9, take 3. Compare 27 and 9, take 9. Compare 27 and 10, take 10. Compare 27 and 82, take 27, then 38, then 43, and 82 is left standing on its own.

Merge Sort in Python, Step by Step

Here is the complete version. It copies the input first, so the caller's list never changes:

def merge_sort(numbers): a = numbers[:] if len(a) <= 1: return a mid = len(a) // 2 left = merge_sort(a[:mid]) right = merge_sort(a[mid:]) out, i, j = [], 0, 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 += left[i:] out += right[j:] return out print(merge_sort([38, 27, 43, 3, 9, 82, 10])) print(merge_sort([5, 2, 4, 6, 1, 3])) 

Output:

[3, 9, 10, 27, 38, 43, 82] [1, 2, 3, 4, 5, 6] 

The function calls itself, which is recursion. Each call splits its list at the middle with len(a) // 2 and sorts the two halves the same way. The base case is a list of one value or less, which is already sorted and returned as it is. The merge loop is where the sorting happens: two pointers, i and j, watch the fronts of the left and right halves, and while both halves still have values the smaller front value is appended to the output. When one half runs out, the rest of the other half is already sorted, so it is tacked on in one go. The <= keeps the sort stable: equal values from the left half go first.

Terminal listing of the real merge sort run tested for this article: the list [38, 27, 43, 3, 9, 82, 10] sorted with 13 comparisons, an already sorted list needing only 9, and merge sort taking 1.80 ms against 0.18 ms for sorted() on 1000 items

A terminal listing of the real merge sort run tested for this article: 13 comparisons on the example list, 9 on already sorted input, and the timing test against sorted().

Counting the Comparisons

Counting comparisons makes the speed concrete. The same function with one counter added gave this real result on our example list:

Result: [3, 9, 10, 27, 38, 43, 82] Comparisons: 13 

Thirteen comparisons for seven values, against 21 for both our bubble sort explained with simple Python examples and our selection sort explained with simple Python examples on the same list. Merge sort does less work because it never compares a value with the whole list, only with the front of the other half.

Sorted input barely changes the bill. The already sorted list [1, 2, 3, 4, 5, 6, 7] still took 9 comparisons, because every merge still has to check the fronts. That is the honest trade: merge sort is fast and steady, but it gets no discount for nearly sorted data.

Best Case, Worst Case and Time Complexity

Halving the list gives about log n levels of splitting, and each level merges every value once, so the total is n times log n comparisons on every input. Extra memory is O(n), because the merges build new lists.

Case Time What happens
Best case O(n log n) Sorted input still merges every level
Worst case O(n log n) Reversed input costs no extra
Extra memory O(n) Each merge builds a new list

A timing test on 1,000 random numbers (seed 42, so the run can be repeated) put numbers on it: our merge sort took 1.80 ms, while Python's built in sorted() took 0.18 ms, about ten times faster. That is no surprise. Python's sorted() uses Timsort, a tuned hybrid that is part merge sort and part insertion sort, written in C. You would never replace sorted() with a hand written version in real code. If Big O itself feels fuzzy, our guide to Big O notation explained simply, with everyday examples builds the idea from scratch.

Merge Sort vs Bubble, Selection and Insertion Sort

Merge sort is the only one of the four that stays at O(n log n) on every input, and the only one that pays for it with extra memory.

Algorithm Time (worst) Extra memory Stable Best for
Merge sort O(n log n) O(n) Yes Large lists, steady speed
Bubble sort O(n^2) O(1) Yes Learning the idea only
Selection sort O(n^2) O(1) No Tiny lists, few swaps
Insertion sort O(n^2) O(1) Yes Nearly sorted data

Pick merge sort when the list is large and you need guaranteed speed. Pick insertion sort when the data is nearly sorted. Pick bubble or selection sort only when you are learning. In real Python code, of course, you just call sorted() and let Timsort do the work.

Common Mistakes and Troubleshooting

Forgetting the base case. If the function never returns a list of length 0 or 1 unchanged, the recursion never stops and Python raises RecursionError.

Losing the leftover values. The merge loop stops as soon as one half runs out. Forget the lines that append the leftovers and the output comes back short. Seven values in and five out is almost always this mistake.

Using < instead of <= and losing stability. With a plain <, equal values from the right half jump ahead of equal values from the left. If the order of equal items matters to you, keep the <=.

Frequently Asked Questions

Is merge sort faster than bubble sort?

Yes, on anything bigger than a tiny list. Merge sort is O(n log n) on every input, while bubble sort is O(n^2). On our seven value example merge sort needed 13 comparisons against bubble sort's 21.

Why does merge sort need extra memory?

Because each merge builds a new output list instead of moving values around inside the original one. That costs O(n) extra memory, which is the price of its steady speed.

Is merge sort stable?

Yes, when it is written with <= so equal values from the left half go first. Stability matters when you sort by one key and want the previous order kept for equal keys.

When should I actually use merge sort?

When you need guaranteed O(n log n) speed on a large list and can afford the extra memory, or when stability matters. In everyday Python, use sorted() instead: it is a tuned version of the same idea, written in C, and about ten times faster.

Conclusion

Merge sort trades memory for steady speed: split the list in half until the pieces are trivial, then merge the sorted pieces by always taking the smaller front value. It costs O(n log n) on every input, it is stable, and it needs O(n) extra memory. You will rarely write it by hand, because sorted() already does the job faster, but understanding it explains why sorted() is fast.