Merge Sort
Merge sort is the textbook divide-and-conquer algorithm. It guarantees O(n log n) performance on every input, uses a stable sort, and its merge step is so useful that it appears as a standalone technique in problems like "count inversions" and "sort linked lists."
Understanding merge sort deeply — not just the code, but the recurrence and the merge step — will make you a stronger programmer.
The Divide and Conquer Strategy
Merge sort follows three steps:
- Divide — split the array in half at the midpoint
- Conquer — recursively sort each half
- Combine — merge the two sorted halves into one sorted array
The magic happens in the merge step. Merging two sorted arrays of total size n takes O(n) time: compare the front elements of each half, take the smaller one, advance that pointer, repeat.
The recurrence is: T(n) = 2T(n/2) + O(n)
By the Master Theorem (case 2): T(n) = O(n log n)
Top-Down Merge Sort (Recursive)
// Top-down merge sort — natural recursive structure
function mergeSort(arr) {
if (arr.length <= 1) return arr; // base case
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid)); // sort left half
const right = mergeSort(arr.slice(mid)); // sort right half
return merge(left, right); // merge sorted halves
}
// Merge two sorted arrays into one sorted array
function merge(left, right) {
const result = [];
let i = 0, j = 0;
// Compare front elements, take the smaller
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) { // <= ensures stability
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
// Append remaining elements (one array is exhausted)
while (i < left.length) result.push(left[i++]);
while (j < right.length) result.push(right[j++]);
return result;
}
mergeSort([38, 27, 43, 3, 9, 82, 10]);
// Split: [38,27,43] and [3,9,82,10]
// Split: [38,27] and [43] → [27,38] and [43] → [27,38,43]
// Split: [3,9] and [82,10] → [3,9] and [10,82] → [3,9,10,82]
// Merge: [27,38,43] and [3,9,10,82] → [3,9,10,27,38,43,82]mergeSort([38,27,43,3,9,82,10]) → [3,9,10,27,38,43,82]
In-Place Merge Sort (Avoids New Arrays)
// In-place version — sorts arr[lo..hi] in place using auxiliary array
// O(n) extra space still needed for the merge buffer
function mergeSortInPlace(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return;
const mid = lo + Math.floor((hi - lo) / 2);
mergeSortInPlace(arr, lo, mid);
mergeSortInPlace(arr, mid + 1, hi);
mergeInPlace(arr, lo, mid, hi);
}
function mergeInPlace(arr, lo, mid, hi) {
// Copy into temporary arrays
const left = arr.slice(lo, mid + 1);
const right = arr.slice(mid + 1, hi + 1);
let i = 0, j = 0, k = lo;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) arr[k++] = left[i++];
else arr[k++] = right[j++];
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}
const arr = [5, 2, 8, 1, 9, 3];
mergeSortInPlace(arr);
// arr is now [1, 2, 3, 5, 8, 9]Bottom-Up Merge Sort (Iterative)
The bottom-up approach avoids recursion entirely by starting with pairs, then quads, then octets, doubling the run length at each pass. This is the basis of Tim Sort and works well for linked lists.
// Bottom-up merge sort — no recursion, iterative passes
function mergeSortBottomUp(arr) {
const n = arr.length;
// Start with runs of size 1, double each pass
for (let size = 1; size < n; size *= 2) {
// Merge adjacent runs of the current size
for (let lo = 0; lo < n - size; lo += size * 2) {
const mid = lo + size - 1;
const hi = Math.min(lo + size * 2 - 1, n - 1);
mergeInPlace(arr, lo, mid, hi);
}
}
return arr;
}
// Example trace for [5, 2, 8, 1, 9, 3, 7, 4]:
// Pass size=1: merge (5,2), (8,1), (9,3), (7,4) → [2,5, 1,8, 3,9, 4,7]
// Pass size=2: merge (2,5,1,8), (3,9,4,7) → [1,2,5,8, 3,4,7,9]
// Pass size=4: merge (1,2,5,8,3,4,7,9) → [1,2,3,4,5,7,8,9]Sorting a Linked List with Merge Sort
Merge sort is the preferred algorithm for sorting linked lists because:
- It only needs sequential access (no random index jumping like quicksort needs)
- The merge step is O(1) space for linked lists (just relink pointers, no copying)
- This makes merge sort O(n log n) time, O(log n) space on linked lists
// LeetCode 148 — Sort List
class ListNode {
constructor(val, next = null) { this.val = val; this.next = next; }
}
function sortList(head) {
if (!head || !head.next) return head; // base case: 0 or 1 node
// Find midpoint using fast-slow pointers
let slow = head, fast = head.next;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
const mid = slow.next;
slow.next = null; // split the list into two halves
const left = sortList(head);
const right = sortList(mid);
return mergeLinkedLists(left, right);
}
function mergeLinkedLists(l1, l2) {
const dummy = new ListNode(0);
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 || l2; // attach remaining nodes
return dummy.next;
}Count Inversions
An inversion in an array is a pair (i, j) where i < j but arr[i] > arr[j] — an element that is "out of order" relative to a later element. The number of inversions measures how "unsorted" an array is. Merge sort counts them in O(n log n).
Key insight: during the merge step, when we take an element from the right half, it means all remaining elements in the left half are greater than it — each forms an inversion.
// Count inversions in O(n log n)
function countInversions(arr) {
let inversions = 0;
function mergeCount(arr, lo, mid, hi) {
const left = arr.slice(lo, mid + 1);
const right = arr.slice(mid + 1, hi + 1);
let i = 0, j = 0, k = lo;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
// left[i] > right[j]: every remaining element in left is > right[j]
inversions += left.length - i; // count all inversions at once
arr[k++] = right[j++];
}
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}
function sortAndCount(arr, lo, hi) {
if (lo >= hi) return;
const mid = lo + Math.floor((hi - lo) / 2);
sortAndCount(arr, lo, mid);
sortAndCount(arr, mid + 1, hi);
mergeCount(arr, lo, mid, hi);
}
const copy = [...arr];
sortAndCount(copy, 0, copy.length - 1);
return inversions;
}
countInversions([2, 4, 1, 3, 5]); // → 3 (pairs: (2,1), (4,1), (4,3))
countInversions([1, 2, 3, 4, 5]); // → 0 (already sorted)
countInversions([5, 4, 3, 2, 1]); // → 10 (reverse sorted = maximum inversions = n*(n-1)/2)countInversions([2,4,1,3,5]) → 3 countInversions([5,4,3,2,1]) → 10
Complexity Analysis
Time: O(n log n) — guaranteed for all inputs, no pathological worst case
Space: O(n) — temporary arrays for the merge step
Stack: O(log n) — recursive call depth (log₂ n splits before reaching size 1)
Stable: Yes — left[i] <= right[j] means equal elements from the left appear first
In-place variant: O(1) extra space exists but is O(n²) time — not practical