Merge Sort — Algorithm Visualized
Learn merge sort — divide and conquer, stable O(n log n) merge, recursive split visualizer, code breakdown, and complexity analysis.
Introduction
Merge sort divides the array in half until subarrays of length 1, then merges sorted halves in O(n) per level — guaranteed O(n log n), stable, predictable performance.
Quick index
| # | Section |
|---|---|
| 1 | How it works |
| 2 | Interactive visualizer |
| 3 | Full implementation |
| 4 | Complexity analysis |
| 5 | Real-life examples |
1. How it works
Divide: [38, 27, 43, 3] → [38,27] [43,3] → [38][27][43][3]
Conquer: merge pairs → [27,38] [3,43] → [3,27,38,43]2. Interactive visualizer
Merge Sort — Step Visualizer
Divide the array in half recursively, then merge sorted subarrays.
Unsorted
n = 7 elements
Divide
mergeSort(arr): split at mid, recurse, merge halves
Split until subarrays of length 1.
Time
O(n log n)
Space
O(n)
Stable
Yes
3. Full implementation
function mergeSort(arr) {
if (arr.length <= 1) return arr
const mid = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, mid))
const right = mergeSort(arr.slice(mid))
return merge(left, right)
}
function merge(left, right) {
const result = []
let i = 0,
j = 0
while (i < left.length && j < right.length) {
result.push(left[i] <= right[j] ? left[i++] : right[j++])
}
return result.concat(left.slice(i)).concat(right.slice(j))
}Function calls with output
// ── Demo calls — output shown on the right ──
const arr = [5, 3, 8, 1, 9, 2, 7]
mergeSort(arr) // → [1, 2, 3, 5, 7, 8, 9]
mergeSort([38, 27, 43, 3]) // → [3, 27, 38, 43]4. Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n log n) always |
| Space | O(n) auxiliary (merge buffer) |
| Stable | Yes |
| Parallel | Easy to parallelize merge step |
5. Real-life examples
| Scenario | Why merge sort |
|---|---|
| Git merge | Combine two sorted commit histories — same merge logic |
| Merging sorted CSV exports | Jan + Feb sales files, both sorted by date |
| External sort (disk) | Sort 100GB file that doesn't fit in RAM — merge sorted chunks |
| Stable sort required | Sort employees by dept, preserve hire-date order within dept |
| Parallel sorting on multi-core | Split array across cores, merge results |
Merge sorted CSV exports
Combine January and February sales files — both already sorted by timestamp.
Two API pages — each sorted by timestamp ascending.
Real-world implementation
function merge(left, right, key = "ts") {
const out = []
let i = 0, j = 0
while (i < left.length && j < right.length) {
if (left[i][key] <= right[j][key]) out.push(left[i++])
else out.push(right[j++])
}
return out.concat(left.slice(i)).concat(right.slice(j))
}Full working code for the scenario above.
Function calls with output
// ── Function calls with output ──
const page1 = [{ ts:100, val:5 }, { ts:200, val:3 }]
const page2 = [{ ts:150, val:8 }, { ts:250, val:1 }]Side output shows return value after each call — step through to trace execution.
Summary
Merge sort guarantees O(n log n) and stability — ideal when worst-case matters or merging sorted lists.
Next reads: Quick Sort · Counting Sort
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime