Merge Sort Visualization & Step-by-Step Simulator

Q: What is the time complexity of merge sort?

O(n log n) in the best, average and worst cases. It needs O(n) extra space.

About this visualization

Merge sort is a divide-and-conquer algorithm: split the list in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front item. It guarantees $O(n \log n)$ time but needs extra memory. The simulator shows the halves being copied and merged.

How it works

Split the list until every piece has one item (a sorted list).
Merge two sorted pieces by comparing their front items.
Merging continues up until the whole list is merged.

Worked example

Sort [38, 27, 43, 3]. Split into [38, 27] and [43, 3]. Merge each: [27, 38] (1 comparison) and [3, 43] (1 comparison). Final merge compares 27 vs 3, 27 vs 43, 38 vs 43 → [3, 27, 38, 43] with 3 more comparisons: 5 comparisons and 8 writes overall.

Enter these numbers in the simulator above to see every step.

Complexity and properties

Best case	$O(n \log n)$
Average case	$O(n \log n)$
Worst case	$O(n \log n)$
Space	$O(n)$
Stable	Yes
In-place	No (needs extra memory)

Needs an auxiliary array for merging.

When to use it

Sorting large lists with guaranteed $O(n \log n)$ performance.
Sorting linked lists and external (on-disk) data.
Learning recursion and divide and conquer.

Frequently asked questions

What is the time complexity of merge sort?

$O(n \log n)$ in the best, average and worst cases. It needs $O(n)$ extra space.

Is merge sort stable?

Yes, if the merge step takes from the left half when items are equal.

Why is merge sort $O(n \log n)$ ?

The list is halved log₂ n times, and each level of merging touches all n items.