Loading algorithms…

Loading visualizer…

Algorithms/Sorting/Merge Sort

Merge Sort

Divide-and-conquer sorting that recursively halves the array and merges the sorted pieces. Guaranteed O(n log n) and stable.

SortingDivide & ConquerStableO(n log n)
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.
1 / 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.
←Previous Algorithm
Prim's MST
GraphO(E log V)
Next Algorithm→
Quick Sort
O(n log n) avgSorting

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