Merge sort, explained

Merge sort uses a divide and conquer idea. A list of one item is already sorted, so it keeps splitting the list until every piece has one item, then merges the pieces back together in order.

Merging two sorted lists is easy: you only compare the front items and always take the smaller one.

How it works

• Split the list into two halves.
• Sort each half the same way, by splitting again until a piece has one item.
• Merge two sorted halves by repeatedly taking the smaller of the two front items.
• Continue merging until you have one sorted list.

A small example

Sort this list:

38 27 43 3

Split:   [38 27]  [43 3]
Sort:    [27 38]  [3 43]
Merge:   3 27 38 43

What to know about its cost

• O(n log n) in the best, average and worst case.
• Needs O(n) extra space for merging.
• Stable: equal items keep their original order.

Where it works well

• Predictable speed, whatever the input.
• Stable, which matters when sorting records.

Where it struggles

• Needs extra memory.
• Slower than simple sorts on very small lists.

Try it yourself

Open the Sorting experiment, enter a list of 8 or more numbers, choose Merge Sort and step through it. Then use the comparison view to run another algorithm on the same list and compare the comparisons and swaps.

Open the Sorting experiment