Loading algorithms…

Loading visualizer…

Algorithms/Sorting/Merge Sort

Merge Sort

Divide-and-conquer sorting that guarantees O(n log n) time. Stable, predictable, and widely used in production.

Divide & ConquerStableRecursive
Comparisonsso far
0
Writesso far
0

Memory Layout

Main array + auxiliary buffer used by the merge step

default comparing swapping sorted
Main arrayin-place
Arrayn = 24
10
21
32
43
54
65
76
87
98
109
1110
1211
1312
1413
1514
1615
1716
1817
1918
2019
2120
2221
2322
2423
✓
RecursionAll sorted — no active range.
0 / 0
Speed
Preset
n24
merge-sort.js
1function mergeSort(arr, lo, hi) {
2 if (lo >= hi) return; // base case
3 
4 // DIVIDE: split the range in half
5 const mid = Math.floor((lo + hi) / 2);
6 mergeSort(arr, lo, mid); // sort left half
7 mergeSort(arr, mid + 1, hi); // sort right half
8 
9 // CONQUER: merge the two sorted halves
10 merge(arr, lo, mid, hi);
11}
12 
13function merge(arr, lo, mid, hi) {
14 // Copy both halves into auxiliary buffers
15 const left = arr.slice(lo, mid + 1);
16 const right = arr.slice(mid + 1, hi + 1);
17 
18 let i = 0, j = 0, k = lo;
19 while (i < left.length && j < right.length) {
20 if (left[i] <= right[j]) {
21 arr[k++] = left[i++];
22 } else {
23 arr[k++] = right[j++];
24 }
25 }
26 while (i < left.length) arr[k++] = left[i++];
27 while (j < right.length) arr[k++] = right[j++];
28}

Algorithm Explanation

Merge sort is a divide-and-conquer algorithm that recursively splits the array in half, sorts each half, and merges the two sorted halves back together. Invented by John von Neumann in 1945, it's the canonical O(n log n) comparison sort and one of the pillars of standard library implementations.

⚙️ How It Works

  1. Divide — split the range [lo…hi] at the midpointmid = ⌊(lo+hi)/2⌋.
  2. Conquer — recursively sort the left half [lo…mid] and the right half [mid+1…hi]. Each recursive call halves the range, so the depth of recursion is⌈log₂ n⌉.
  3. Combine — at each level, walk both sorted halves in parallel with two pointers. At every step, copy the smaller of the two front elements into the output slot and advance that pointer. Once one half drains, copy the rest of the other.
  4. Base case — a range of length 0 or 1 is already sorted; the recursion bottoms out.

🧩 Why a buffer?

The merge phase needs to look at both halves simultaneously while writing back into the same array, which would clobber unread data. The textbook solution is to copy each half into an auxiliary buffer first, then walk those buffers with two pointers. This costs O(n) extra space but lets the merge run in a single linear pass per level.

💡 Stability: Merge sort preserves the relative order of equal elements — useful when sorting records by a secondary key (e.g. users by last name, then by first name). Quick sort, by contrast, is not stable in its standard in-place form.

⚖️ Merge vs Quick vs Heap

Merge sort (this page)
  • Guaranteed O(n log n).
  • Stable — preserves order of equals.
  • Needs O(n) extra buffer.
  • Great for linked lists & external sort.
Quick sort
  • O(n log n) average, O(n²) worst case.
  • Not stable by default.
  • In-place (O(log n) stack).
  • Faster in practice on random data due to cache locality.
Heap sort
  • Guaranteed O(n log n).
  • Not stable.
  • In-place (O(1) extra).
  • Worse cache behaviour than quick / merge sort.

Watch the recursion split the array at depth ⌈log₂ n⌉, then merge the sorted pieces back together.

About the Merge Sort algorithm

Divide-and-conquer sorting that guarantees O(n log n) time. Stable, predictable, and widely used in production.

Category
Sorting
Difficulty
Medium
Time complexity
O(n log n)
Space complexity
O(n)
Introduced
1945
←Previous Algorithm
Cycle Detection (Directed)
GraphO(V+E)
Next Algorithm→
Quick Sort
O(n log n) avgSorting