Merge sort is the classic divide and conquer sort. It splits the array into two halves, sorts each half recursively, then merges the two sorted halves into one. This visualizer highlights the part of the array being worked on, shows the temp array used during each merge, and animates every comparison and write back into the array.
Unlike the simple O(n²) sorts, merge sort always takes O(n log n) time, whatever the input: random, sorted or reversed. The price is extra memory for the temp array. Watch the write counter: every level of the recursion writes all n values once, and there are about log₂ n levels.
How to use the Merge Sort Visualizer tool
- Pick an array size and an input: random, nearly sorted, reversed or few unique values. You can also type your own numbers.
- Press Play to watch the sort, or Step to move one comparison or swap at a time. Back goes one step back.
- Follow the colours: orange bars are being compared, red bars are being swapped or written, green bars are in their final place.
- Read the message under the controls and the highlighted pseudocode line to see exactly what the algorithm is doing.
- Change the speed, switch the code tab to C++, Java, Python or JavaScript, and compare the counters with other inputs.
Why use ToolOrca Merge Sort Visualizer
- Animated bars with play, pause, step and step back
- Speed slider and a position slider to jump to any step
- Temp array shown during every merge
- Comparison and swap counters
- Random, nearly sorted, reversed and few-unique inputs, or your own numbers
- Highlighted pseudocode line for every step
- Code in C++, Java, Python and JavaScript
- Works on phones and tablets, keyboard accessible
How merge sort works
Divide: split the range lo..hi at mid = (lo + hi) / 2. Conquer: sort lo..mid and mid + 1..hi recursively; a range of one element is already sorted. Combine: merge the two sorted halves. Copy them to a temp array, then repeatedly compare the front values of the two halves and write the smaller one back to the array. When one half runs out, copy the rest of the other.
Taking the left value when the two are equal keeps merge sort stable, which is why it is used to sort records by several keys.
Time and space complexity of merge sort
Each level of splitting does O(n) work to merge, and halving n repeatedly gives log₂ n levels, so merge sort runs in O(n log n) in the best, average and worst case. Sorting a million values takes about 20 million steps instead of 500 billion for an O(n²) sort. The array version needs O(n) extra memory for the temp array; linked lists can be merge sorted with O(1) extra memory.
When to use merge sort
Use merge sort when you need guaranteed O(n log n) time, a stable sort, or to sort a linked list or data too big for memory (external sorting merges sorted chunks from disk). Java uses a merge sort variant (Timsort) for objects and Python’s sorted() is Timsort too. When memory is tight and stability does not matter, quick sort or heap sort may be better.
Every visualizer on this site runs in your browser with the same controls: Play, Pause, Step forward, Step back and a speed slider. You can also drag the position slider to jump to any step, or focus the drawing and use the Space bar and arrow keys.
Frequently asked questions
What is the time complexity of merge sort?
O(n log n) in every case, because it always splits in half and always merges all n values on each of the log n levels.
How much extra memory does merge sort need?
O(n) for the temporary array used while merging, plus O(log n) for the recursion stack.
Is merge sort stable?
Yes, as long as the merge takes from the left half when the two front values are equal.
Merge sort or quick sort: which is faster?
Quick sort is usually faster in practice on arrays because it sorts in place and uses the cache well, but it has an O(n²) worst case. Merge sort is always O(n log n) and stable, but needs extra memory.