A stable, divide-and-conquer sorting algorithm. It divides the array into halves, sorts them, and then merges the sorted halves.
Parameters
16
Visualization
Step: 0
Divide and conquer! Sorting by merging sub-arrays.
Algorithm Insight
Merge Sort is a Divide and Conquer algorithm that guarantees efficiency.
1.Divide the unsorted list into $n$ sublists (size 1).
2.Repeatedly merge sublists to produce new sorted sublists.
3.The final merge results in a fully sorted array.
4.Stable sort: keeps original order of equal elements.
Complexity
Time ComplexityO(N log N)
Space ComplexityO(N)
Overview
Merge sort divides an array into halves, sorts each half recursively, then merges the sorted halves. Its running time is O(n log n) in every case; the usual array implementation needs O(n) extra space for merging.
The merge is the whole algorithm
Merging two sorted arrays is linear. Keep a finger on the front of each; repeatedly take the smaller of the two and advance that finger. Merge [2, 5, 9] with [1, 6, 8]:
compare 2 vs 1 → take 1 [1]
compare 2 vs 6 → take 2 [1, 2]
compare 5 vs 6 → take 5 [1, 2, 5]
compare 9 vs 6 → take 6 [1, 2, 5, 6]
compare 9 vs 8 → take 8 [1, 2, 5, 8]
left only → append 9 [1, 2, 5, 6, 8, 9]
Six elements, five comparisons. Each comparison places exactly one element, so merging two runs of total length n costs at most n−1 comparisons and exactly n writes.
Where n log n comes from
Halving the array repeatedly gives log₂n levels of recursion — 32 elements become 16, 8, 4, 2, 1, which is 5 levels. At every level, the merges together touch all n elements exactly once. So:
total work = n per level × log2(n) levels = O(n log n)
The recurrence is T(n) = 2T(n/2) + O(n), which is the standard case of the master theorem giving Θ(n log n). Crucially this holds for every input — the split is positional, not value-dependent, so there is no bad pivot and no worst case. Sorted, reversed and random input all cost the same.
Split, sort, merge
Merge sort is divide and conquer in its cleanest form:
Divide. Split the array in half. Conquer. Sort each half recursively. Combine. Merge the two sorted halves.
The base case is an array of one element, which is sorted by definition. All the work is in the merge.
Sorting [38, 27, 43, 3]:
Level
State
Split
[38, 27] [43, 3]
Split
[38] [27] [43] [3]
Merge
[27, 38] [3, 43]
Merge
[3, 27, 38, 43]
The recursion has log n levels, and each level does O(n) work merging — hence O(n log n), for every input, with no bad cases.
The cost: O(n) extra space
Merging cannot be done in place without a substantial loss of simplicity or speed. The straightforward implementation allocates a new array at each merge, using O(n) additional memory.
That is merge sort's main disadvantage against quick sort, and it is what decides between them for in-memory array sorting.
Merge sort
Quick sort
Worst case
O(n log n) guaranteed
O(n²)
Extra space
O(n)
O(log n)
Stable
Yes
No
Cache behaviour
Good
Excellent
Linked lists
Ideal — O(1) extra
Poor — needs random access
External sorting
Ideal
Poor
The linked-list row is worth noting: merging two linked lists requires only pointer rearrangement, so merge sort on a linked list uses O(1) extra space and is the natural choice there.
Experiments to try with Merge Sort
Watch the recursion bottom out. Set Array Size to 16 and press Next Step repeatedly. The array splits until every block holds one element, and only then does anything get compared. All the sorting happens on the way back up.
Count the levels. At Array Size 16 there are 4 levels of merging; at 32 there are 5. Doubling the array adds one level, and each level costs a full pass — that is n log n, split into its two factors.
The memory cost, and why it is unavoidable
Merging in place is the hard part. To write the smaller element into position 0 you must first move whatever already occupies position 0, and doing that without a buffer requires shifting — which turns the linear merge quadratic.
So standard merge sort allocates an auxiliary array of size n, giving O(n) space. In-place merge sort algorithms exist, but they trade the clean linear merge for substantially worse constants and considerably more complexity. In practice, if memory is the constraint you use quick sort or heap sort instead.
The exception is linked lists, where merging needs only pointer reassignment and no buffer. Merge sort on a linked list is O(1) extra space, which is why it is the standard list-sorting algorithm.
Continue with quicksort, which builds on this idea.
Run it in Python
The recursion prints its own indentation, so the split-then-merge shape is visible in the output. The merge step is where the sorting actually happens — splitting a list in half does no work at all.
merge_sort.pyPython 3
# Merge sort: split until the pieces are trivially sorted, then merge.
def merge(left, right, key):
out = []
i = j = 0
while i < len(left) and j < len(right):
if key(left[i]) <= key(right[j]): # <= keeps equal items in order
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:]) # one side is empty; drain the other
out.extend(right[j:])
return out
def merge_sort(a, key=lambda x: x, depth=0, show=True):
pad = " " * depth
if len(a) <= 1: # a single item is already sorted
if show:
print(f"{pad}{a} (base case)")
return a
mid = len(a) // 2
if show:
print(f"{pad}split {a} -> {a[:mid]} + {a[mid:]}")
left = merge_sort(a[:mid], key, depth + 1, show)
right = merge_sort(a[mid:], key, depth + 1, show)
out = merge(left, right, key)
if show:
print(f"{pad}merge {left} + {right} -> {out}")
return out
data = [38, 27, 43, 3, 9, 82, 10]
print("start :", data)
print()
result = merge_sort(data)
print()
print("sorted:", result)
# Stability, run through this same code rather than asserted.
pairs = [("b", 2), ("a", 1), ("c", 2), ("d", 1)]
print()
print("by number:", merge_sort(pairs, key=lambda p: p[1], show=False))
print("a before d, b before c - ties kept the order they arrived in")
Output
How the code works
if len(a) <= 1: return aThe base case. A list of one is sorted by definition, and every branch of the recursion bottoms out here — which is why merge sort needs no explicit termination check.
mid = len(a) // 2The split is positional and costs nothing to choose. Contrast quicksort, where choosing the split point is the algorithm and a bad choice costs O(n²).
while i < len(left) and j < len(right):Both halves are already sorted, so the next smallest item overall is always at the front of one of them. That single fact is why merging is linear.
if left[i] <= right[j]:The <= is what makes merge sort stable: on a tie the left half wins, and the left half held the earlier items. Change it to < and stability is gone, silently.
out.extend(left[i:]); out.extend(right[j:])When one side runs out the other is already sorted and every item in it is larger, so it can be appended wholesale. One of these two lines is always a no-op.
Change one thing
Change <= to < in merge, then sort a list with duplicates and watch stability break.
Count the merge lines the program prints. It is about n log n for any input — merge sort has no best case, and no worst case either.
Replace the slices with index ranges into one shared list. That removes the O(n) copies, and shows why the classic implementation needs O(n) extra space.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Predict, then reveal
About to run: Watch the recursion bottom out. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
Where does the actual sorting happen in merge sort?
Splitting a list in half is positional and does no comparing. All the ordering work is in combining two sorted halves.
In merge, why is the comparison left[i] <= right[j] rather than < ?
On a tie the left half wins, and the left half held the earlier items. Changing it to < breaks stability silently, with no other visible symptom.
Merge sort's worst case compared with its best case:
It has no pivot to choose badly and no early exit to hit. That predictability is exactly why it is used where worst-case latency matters.
Cheat sheet
Merge Sort
Split an array down to single elements and watch merge sort combine sorted halves back together in n log n time.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.