A stable, divide-and-conquer sorting algorithm. It divides the array into halves, sorts them, and then merges the sorted halves.
Overview
Divide, conquer, combine
Merge sort is the textbook divide-and-conquer algorithm and it has exactly three steps. Divide: split the array at the midpoint. Conquer: sort each half by calling merge sort on it. Combine: merge the two sorted halves into one sorted array.
The recursion bottoms out at arrays of length one, which are sorted by definition. All the real work happens in the merge, on the way back up.
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)
Merge Sort: A Practical Guide
Split the array in half, sort each half, then merge the two sorted halves. Guaranteed O(n log n) on every input, stable, and the reason it costs O(n) extra memory.
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.
Merging is the whole algorithm
Given two sorted lists, produce one sorted list by repeatedly taking the smaller of the two front elements:
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= is what makes it stable
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:]) # whatever remains is already sorted
out.extend(right[j:])
return out
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
The <= on line 4 is not arbitrary. With <=, when two elements are equal the one from the left half is taken first — and since the left half came earlier in the original array, equal elements keep their relative order. That is stability, and changing <= to < silently destroys it.
Stability matters more than it sounds. Sorting a table by surname and then by department gives a list ordered by department, and alphabetical within each department — only if the second sort is stable.
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.
The guarantee, and what it costs
Merge sort's selling point is not that it is fast on average -- quick sort usually beats it -- but that its worst case equals its best case. Here is that guarantee measured against quick sort's on the input designed to break it, along with the price merge sort pays in memory.
example_01.pyPython
def merge_sort(a, stats):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid], stats)
right = merge_sort(a[mid:], stats)
stats["allocated"] += len(a) # the merge buffer for this level
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
stats["comps"] += 1
if left[i] <= right[j]: # <= keeps equal elements in order
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:]); out.extend(right[j:])
return out
def quick_sort(a, stats, depth=0):
stats["depth"] = max(stats["depth"], depth)
if len(a) <= 1:
return a
pivot = a[-1] # last element: the naive choice
lo, eq, hi = [], [], []
for x in a:
stats["comps"] += 1
(lo if x < pivot else hi if x > pivot else eq).append(x)
return quick_sort(lo, stats, depth + 1) + eq + quick_sort(hi, stats, depth + 1)
import random
random.seed(11)
n = 64
inputs = {
"random": random.sample(range(n), n),
"sorted": list(range(n)),
"reversed": list(range(n))[::-1],
}
print("n = %d" % n)
print("%-10s %12s %12s" % ("input", "merge comps", "quick comps"))
for name, data in inputs.items():
ms = {"comps": 0, "allocated": 0}
qs = {"comps": 0, "depth": 0}
merge_sort(data, ms)
quick_sort(data, qs)
print("%-10s %12d %12d" % (name, ms["comps"], qs["comps"]))
# Merge sort's column stays inside a narrow band -- 192 to 304, against a
# ceiling of n log2 n = 384 -- because the split is positional, so the
# shape of the data cannot change how many levels there are. Quick sort
# with a last-element pivot does not have that protection: on sorted and
# reversed input every partition peels off exactly one element, and 375
# comparisons become 2079 -- one short of n(n+1)/2, the quadratic sum,
# rather than anything resembling n log n.
import math
print()
print("n log2 n = %.0f" % (n * math.log2(n)))
# Now the cost. Merge sort allocates a buffer at every level.
for name, data in inputs.items():
ms = {"comps": 0, "allocated": 0}
merge_sort(data, ms)
print("%-10s allocated %d slots for %d elements (n log2 n = %.0f)" % (
name, ms["allocated"], n, n * math.log2(n)))
# That is the O(n log n) total allocation people mean when they say merge
# sort needs O(n) extra space -- O(n) live at any moment, since each level
# is freed before the next, but the allocation traffic is real and it is
# why merge sort loses to quick sort on cache-friendliness.
#
# What you buy with it, besides the guarantee, is stability.
pairs = [(x, i) for i, x in enumerate([3, 1, 3, 1, 2])]
print()
print("input (value, original index):", pairs)
print("merge sorted by value: ",
merge_sort(pairs, {"comps": 0, "allocated": 0}))
# The two 3s come out with original indices 0 then 2, and the two 1s as
# 1 then 3 -- input order preserved within equal keys. That is the <= in
# the merge comparison; with < the equal element from the right half
# would be taken first and stability would be gone.
Output
Experiments to try
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.
Give it sorted input. Press Randomize Array until the array is close to ascending and press Auto-Run. The step count barely moves. Unlike quick sort, merge sort has no input that hurts it.
Spot the extra array. Watch a merge closely: elements are written to a separate buffer and then copied back. That buffer is the O(n) auxiliary memory, and it is not an implementation detail you can optimise away.
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.
Where this goes wrong
Allocating a new buffer per recursive call. This turns O(n) space into O(n log n) and hammers the allocator. Allocate one buffer up front and pass it down.
Breaking stability with < instead of ≤. When the two fronts are equal the merge must take from the left run. Using a strict comparison that prefers the right run reverses equal elements and silently destroys stability.
Forgetting the leftover tail. When one run empties, the remainder of the other must be copied across. Dropping that step truncates the output.
Recursing all the way to size 1. The call overhead dominates on tiny subarrays. Real implementations switch to insertion sort below roughly 16 elements, which typically buys 10–20%.
Key takeaway
Merge sort splits positionally, sorts recursively, and does its real work in a linear merge, giving a guaranteed Θ(n log n) on every input with no pathological case. It is stable, it parallelises cleanly, and it is the natural sort for linked lists and for data too large to fit in memory. The price is O(n) auxiliary space for arrays — which is precisely the trade quick sort makes in the opposite direction.
Where the guarantee earns its keep
External sorting. Data too large for memory is sorted by reading chunks, sorting each in memory, writing them back, and then merging the sorted runs in a streaming pass. Merge sort is the only classic algorithm whose access pattern is sequential enough for this, and it is how databases sort large results and how sort handles huge files.
Stability requirements. Multi-key sorting done as successive stable sorts, which is how spreadsheet and dataframe sorting works.
Linked lists. No random access needed, O(1) extra space.
Predictable latency. A guaranteed O(n log n) matters where a worst case would breach a service-level agreement, and quick sort's rare quadratic case is unacceptable.
Parallel sorting. The two halves are independent, so they can be sorted concurrently. Merge sort parallelises naturally in a way quick sort's in-place partitioning does not.
Timsort: what Python actually uses
Python's sorted and list.sort use Timsort, a merge sort adapted for real-world data. Two ideas make it faster than textbook merge sort:
It finds existing runs. Real data is often partially sorted, and Timsort detects ascending or descending runs and merges them rather than splitting down to single elements. On already-sorted input it is O(n).
It uses insertion sort for small runs. Below a threshold (32–64 elements), insertion sort's low constant factor beats recursion.
It is stable, which Python guarantees as part of the language, and its worst case remains O(n log n). Java uses it for object arrays for the same reasons.
The practical lesson: use the library sort. Timsort is better than anything you will write, and it handles the cases that matter.
Questions people ask
Why is merge sort O(n log n) always? Because the split is always exactly in half, independent of the data. Quick sort's split depends on the pivot, which is why its worst case differs.
Can merge sort be done in place? In-place variants exist and are considerably more complex and slower in practice. The O(n) space version is what is used.
Is merge sort stable? Yes, provided the merge takes from the left half on ties. That single comparison decides it.
Why does Python use Timsort rather than quick sort? Stability is a language guarantee, real data is often partially sorted, and the worst case is bounded.
Which is faster in practice? Quick sort, usually, on arrays in memory — better cache behaviour and no allocation. Timsort wins on partially-sorted data.
How does external merge sort work? Sort chunks that fit in memory, write them out, then merge the sorted runs with a k-way merge using a heap.
Recap in one screen
Split in half, sort each half recursively, merge the sorted halves — O(n log n) for every input.
All the work is in the merge, which takes the smaller front element repeatedly.
Taking from the left half on ties is what makes it stable; < instead of <= destroys that.
It needs O(n) extra space, which is its main cost against quick sort.
Ideal for linked lists, external sorting and parallel sorting; Timsort is the production refinement.
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.
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
Merge sort is the textbook divide-and-conquer algorithm and it has exactly three steps. Divide: split the array at the midpoint. Conquer: sort each half by calling merge sort on it. Combine: merge the two sorted halves into one sorted array.
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.