Merge Sort

Task: Sort this array in ascending order

Why we need Merge Sort

A teacher finishes an exam with 200 answer sheets in a messy pile, and they all have to go in order of roll number.
Doing it alone is slow, so the teacher splits the pile in half and hands one half to each of two assistants.
Each assistant does the same thing: split, and pass the halves on. This keeps going until somebody is holding a single sheet, which is already in order by itself.
Now the sheets travel back up. Each person takes the two sorted piles they are handed and combines them into one sorted pile.
The teacher gets back two sorted piles of 100 and combines them into 200. That is merge sort, and there is nothing more to it.

What is merge sort?

Merge sort cuts the list in half until every piece holds one value, then merges the sorted pieces back together.

It rests on a single observation: joining two sorted lists is easy. Sorting from scratch is hard, merging is not.

So the algorithm spends its effort making the problem small enough that sorting is free, and then does the easy thing many times.

The merge, which is the whole algorithm

Forget the splitting for a minute. Put two sorted piles face up on a table, and a finger on the front of each one.

Compare the two fronts, take the smaller, and move that finger along. Repeat.

When one pile runs out, everything left in the other is already sorted and already larger than everything placed so far, so it simply follows.

Now count the work. Every value was looked at once and no value was looked at twice. Merging two piles holding n values between them takes n steps. That one fact is the reason merge sort is fast.

Divide and conquer

That splitting-then-merging shape has a name, and merge sort is the example everyone is taught it with.

Divide and conquer solves a problem in three moves: divide it into smaller problems of the same kind, conquer each one the same way, and combine the answers.

In merge sort the divide is cutting the array in half, the conquer is sorting each half by merge sort, and the combine is the merge.

The third move is where the work is. Dividing decides nothing and costs nothing, and the conquering is just the same instruction again on something smaller. Everything merge sort actually does, it does while combining.

Which answers the question people get stuck on: nobody sorts. The merging is the sorting. Order appears a little at a time, two piles at a time.

Read it top to bottom. Going down, the pieces are cut in half again and again until each one holds a single value, and a single value is in order by definition. Coming back up, neighbouring pieces are merged in pairs until one pile is left.

The row never gets shorter. The only thing that moves is where the boundaries are.

Try it

Try it yourself

Divide down to single values, then merge back up

merge_sort(arr)Step through it, or run one merge at a time

ready

Press step a few times and watch the array come apart. Nothing is compared on the way down: the values only move into smaller and smaller boxes until each box holds one, which is sorted because there is nothing to put it out of order with.

Then the boxes start emptying upward. Every comparison you see happens here, on the way back, and each one moves a single value into its parent's row.

Press merge to finish one box at a time, or sort to run the whole thing.

Why it is always O(n log n)

Two questions, and they are much easier apart than together.

How many levels are there? Each level cuts the pieces in half, so the pieces halve every time: 8, then 4, then 2, then 1. Halving n down to one takes log₂ n steps. A thousand values is only about ten levels deep.

How much does one level cost? Merging a level walks past every value exactly once. So a level costs n, no matter how many pieces that level is cut into.

Multiply the two and you have it: n work on each level, log n levels, so O(n log n) in total.

The part worth remembering is that this is a guarantee. Sorted input, reversed input, random input, every value the same: merge sort takes exactly the same route and pays exactly the same price. Quick sort cannot promise that.

In code

Python

def merge_sort(arr):  if len(arr) <= 1:      return arr  mid = len(arr) // 2  left = merge_sort(arr[:mid])  right = merge_sort(arr[mid:])  return merge(left, right) 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

The <= on the highlighted line is what makes merge sort stable. When the two fronts are equal, the left one is taken first, and the left run came from earlier in the array, so equal values keep the order they arrived in. Change it to < and stability quietly disappears.

Why that matters: sort a class by name, then sort the result by marks. Two students who both scored 85 stay in alphabetical order, because the second sort never reordered them.

What it costs

Case	Time	Space	Why
Best	O(n log n)	O(n)	The splitting and merging happen whatever the input looks like.
Average	O(n log n)	O(n)	log n levels, and all n values merged on every one of them.
Worst	O(n log n)	O(n)	No input makes it slower. There is no bad case to find.

The space is the honest cost. Merging two runs in place is awkward, so the merged values are written into a buffer the size of the input.

Merge sort against quick sort

	Merge sort	Quick sort
Worst case	O(n log n)	O(n²)
Extra memory	O(n)	O(log n)
Stable	Yes	No
In practice	Slower by a constant, because of the copying	Faster: it sorts in place and the cache likes it

Quick sort usually wins on an ordinary array in memory. Merge sort wins when you need the guarantee, when you need stability, or when the data does not fit in memory at all.

Where you have seen it

Sorting a file bigger than memory. Read a chunk, sort it, write it back, then merge the sorted chunks together. A merge only needs a few values in memory at a time, so the file can be any size. Databases do exactly this.
Sorting linked lists. Merging only ever walks forward, so it never needs to jump to the middle. Quick sort does, and a list cannot.
Python's sorted() and Java's Arrays.sort() for objects. Both use Timsort, a merge sort that first looks for stretches already in order.
Measuring how far a list is from sorted. The merge step can count out-of-order pairs almost for free, which is how recommendation systems compare two people's rankings.

Mistakes to watch for

Watch out

Forgetting the base case. With no rule that stops at one value, the function calls itself forever.
Writing < instead of <=. It still sorts, and it silently stops being stable.
Forgetting the leftovers. When one run empties, the rest of the other has to be copied across, or values quietly go missing.
Writing mid = (lo + hi) / 2. On a very large array that sum overflows. Use lo + (hi - lo) / 2 instead.

Quick recap

Cut the list in half until every piece holds one value
Merge neighbouring pieces back together, two at a time
A merge walks both pieces once, so every level costs n
There are log n levels, so the whole sort is n log n, on every input

Sorting is hard and merging is easy. Merge sort spends its effort making the problem small enough that only merging is left.