Merge Sort Algorithm Explained
Merge sort recursively splits a list in half until each piece has one element, then merges the pieces back together in sorted order.
Published November 15, 2026
Merge sort splits the list in half, sorts each half recursively, then merges the two sorted halves into one. It guarantees O(n log n) time and is stable, at the cost of O(n) extra memory.
The concept
Divide until pieces have one element (trivially sorted), then merge pairs: repeatedly take the smaller front item of the two halves.
Its predictable performance makes it ideal for linked lists and external sorting of data too large for memory.
Divide and merge
[6, 2, 8, 4]
[6, 2] [8, 4]
[2, 6] [4, 8] ← sorted halves
[2, 4, 6, 8] ← merged
Practical examples
JavaScript
function mergeSort(a) {
if (a.length < 2) return a
const m = a.length >> 1
const l = mergeSort(a.slice(0, m)), r = mergeSort(a.slice(m))
const out = []
while (l.length && r.length) out.push(l[0] <= r[0] ? l.shift() : r.shift())
return [...out, ...l, ...r]
}Python
def merge_sort(a):
if len(a) < 2: return a
m = len(a)//2
l, r = merge_sort(a[:m]), merge_sort(a[m:])
out = []
while l and r: out.append(l.pop(0) if l[0] <= r[0] else r.pop(0))
return out + l + rComplexity
time O(n log n) always · space O(n) · stableCommon mistakes
- Using shift() (O(n)) in the merge for big arrays.
- Using <, not <=, and breaking stability.
- Ignoring the extra memory.
Key takeaways
- Divide, sort, merge.
- Always O(n log n), stable.
- Needs O(n) extra space.
FAQ
Why is it good for linked lists?
Merging needs no random access or extra array.
Is it faster than quicksort?
Often slightly slower in memory-bound arrays but more predictable.