Merge Sort —
O(n log n), guaranteed, every time.
Merge sort splits the array down to single elements, then merges pairs back together in sorted order — and unlike some faster-looking algorithms, its O(n log n) performance never degrades, no matter what the input looks like. Watch every split and every merge animate on LearnBug and see exactly where the log n comes from.
What is Merge Sort?
A divide-and-conquer sort: split the array in half repeatedly until each piece has 0 or 1 elements (trivially sorted), then merge pairs of sorted pieces back together, comparing their fronts and always taking the smaller one. The merge step is what actually does the sorting work — splitting alone doesn't sort anything.
Why visualization helps
It's easy to see "split then merge" as two separate ideas instead of one continuous recursive process. LearnBug shows the array physically dividing down to single elements and then building back up pair by pair, so you can watch exactly which two pieces are being compared and merged at each moment.
Consistent performance is the whole selling point
No worst-case surprises
Always exactly O(n log n) — best, average, and worst case are identical, because the split is always exactly in half regardless of input order.
Stable — equal elements keep their order
The merge step always takes from the left array on ties, so two equal elements never swap relative positions — important when sorting by one field but needing to preserve another.
The trade-off: O(n) extra space
Unlike quick sort's in-place partitioning, merging allocates new arrays — real memory cost for large datasets, which is the main reason it isn't always the default choice.
Sorting [5, 2, 8, 1, 9, 3]
Split down to single elements: [5,2,8,1,9,3] → 6 arrays of size 1
[5,2,8,1,9,3] splits into [5,2,8] and [1,9,3]; those split again into [5],[2,8] and [1],[9,3]; and so on, until every element is alone. No comparisons or swaps happen during this phase.
Merge adjacent pairs: [5]+[2]→[2,5], [8] alone this round, [1]+[9]→[1,9], [3] alone
This is where sorting actually happens. Comparing 5 and 2, the smaller (2) goes first. [8] and [3] have no partner at this level yet since 6 doesn't split perfectly evenly at every level.
Merge [2,5] with [8] → [2,5,8]; merge [1,9] with [3] → [1,3,9]
Merging [1,9] with [3]: compare 1 vs 3 → take 1. Compare 9 vs 3 → take 3. Only 9 left → take 9. Result: [1,3,9] — this is where 3 moves ahead of 9.
Final merge: [2,5,8] + [1,3,9] → [1,2,3,5,8,9]
1 vs 2 → take 1. 2 vs 3 → take 2. 5 vs 3 → take 3. 5 vs 9 → take 5. 8 vs 9 → take 8. Only 9 left → take 9.
Return: [1, 2, 3, 5, 8, 9] ✓ 3 split levels, 3 merge levels — O(n log n) total
Split, sort recursively, merge
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):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps it stable — ties favor the left array
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([5, 2, 8, 1, 9, 3]))Complexity Notes
Frequently asked questions
Why is merge sort O(n log n) no matter what the input looks like?
The split step always divides exactly in half by index, regardless of the actual values — so the recursion depth (log n) is fixed by the array's length alone. Each level of merging touches every element exactly once (O(n) per level), and there are always log n levels, so the total is O(n log n) for every possible input, including already-sorted or reverse-sorted arrays.
What does "stable" mean and why would I care?
A stable sort guarantees that two elements considered equal by the sort key keep their original relative order. This matters when you're sorting by one field after already having sorted by another — e.g. sort a list of people by last name, then stably sort by first name, and people with the same first name stay ordered by last name.
When would I pick merge sort over quick sort?
When you need a worst-case guarantee (real-time systems, adversarial input), when stability matters, or when sorting linked lists (merge sort doesn't need random access the way quick sort's partitioning does). Quick sort typically wins for general in-memory array sorting due to better cache behavior and lower constant factors.
Can merge sort be done in-place to save the O(n) space?
There are in-place merge sort variants, but they're significantly more complex and typically trade away some of the simple O(n log n) guarantee or add extra time overhead. In practice, the O(n) extra space is usually accepted as merge sort's cost for its stability and worst-case guarantee.
Watch every split and every merge, animated
Paste merge sort into LearnBug and see the array divide and rebuild in sorted order.