ƒ(x) SortingIntermediate interactive
Merge Sort
Divide in half, sort, merge. Guaranteed O(n log n).
merge_sort
step 1 / 85
44
8
18
20
88
94
64
34
50
94
94
Divide the array down to single elements, then merge.
comparingmovingsorted
speed1×
How it works
Merge sort splits the array in half recursively until single elements remain, then merges sorted halves back together. The merge step is linear and the recursion is log n deep, giving a rock-solid O(n log n) in every case — at the cost of O(n) extra space.
Mental models
- Divide-and-conquer: log n levels, O(n) merge work per level.
- Stable, and the go-to for sorting linked lists and external data.
Complexity
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(n)