Merge Sort Explained Step by Step — Why It's Preferred in Interviews
Merge sort is the go-to sorting algorithm for technical interviews because it is always O(n log n), stable, and predictable. Unlike Quick Sort, it never degrades to O(n²) on bad input. This complete guide walks through the divide-and-conquer logic step by step, covers implementations in multiple languages, and explains every related interview problem you need to know.
O(n log n)
time — always, no worst case
O(n)
space — extra array needed
Stable
preserves order of equal elements
Divide & Conquer
split → sort → merge
The Core Idea — Divide and Conquer
Quick fact
Merge sort follows a simple principle: split the array in half, sort each half recursively, then merge the two sorted halves back together. Merging two already-sorted arrays is O(n) — that is the key insight that makes the whole algorithm efficient.
The elegance of merge sort lies in the fact that sorting two halves recursively reduces to the same problem at a smaller scale. Eventually you reach arrays of size 1, which are trivially sorted. Then the merge step builds the sorted result back up from those single elements.
Divide: Split array in half
Keep splitting until each piece has 1 element. A single element is always sorted by definition.
Continue splitting recursively
[38,27,43,3,9,82,10] → [38,27,43] | [3,9,82,10] → [38] | [27,43] → [27] | [43]
Conquer: Merge sorted pairs
Merge [27] + [43] = [27,43]. Then merge [38] + [27,43] = [27,38,43].
Final merge
Merge sorted left half [27,38,43] + sorted right half [3,9,10,82] = [3,9,10,27,38,43,82].
JavaScript Implementation
The implementation has two functions: the recursive mergeSort that splits the array, and the merge function that combines two sorted arrays into one.
function mergeSort(arr) {
// Base case: 0 or 1 element is already sorted
if (arr.length <= 1) return arr;
// Divide
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
// Conquer
return merge(left, right);
}
function merge(left, right) {
const result = [];
let l = 0, r = 0;
// Compare front elements of both arrays, take the smaller
while (l < left.length && r < right.length) {
if (left[l] <= right[r]) {
result.push(left[l++]);
} else {
result.push(right[r++]);
}
}
// Append remaining elements (one array will be exhausted first)
return result.concat(left.slice(l)).concat(right.slice(r));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// → [3, 9, 10, 27, 38, 43, 82]Python Implementation
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
l, r = 0, 0
while l < len(left) and r < len(right):
if left[l] <= right[r]:
result.append(left[l]); l += 1
else:
result.append(right[r]); r += 1
result.extend(left[l:])
result.extend(right[r:])
return result
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]Java Implementation
public static int[] mergeSort(int[] arr) {
if (arr.length <= 1) return arr;
int mid = arr.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
return merge(left, right);
}
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int l = 0, r = 0, i = 0;
while (l < left.length && r < right.length) {
if (left[l] <= right[r]) result[i++] = left[l++];
else result[i++] = right[r++];
}
while (l < left.length) result[i++] = left[l++];
while (r < right.length) result[i++] = right[r++];
return result;
}Why It's Always O(n log n)
The math behind O(n log n)
At each level of recursion, the merge step processes every element exactly once. With log n levels and n work per level, the total work is always n × log n. This is why merge sort is described as guaranteed O(n log n), unlike Quick Sort which can hit O(n²) on already-sorted input with a naive pivot.
mergeSort([38,27,43,3,9,82,10]) ← Level 0: 7 elements
├── mergeSort([38,27,43]) ← Level 1: 3 elements
│ ├── mergeSort([38])
│ └── mergeSort([27,43])
│ ├── mergeSort([27])
│ └── mergeSort([43])
└── mergeSort([3,9,82,10]) ← Level 1: 4 elements
├── mergeSort([3,9])
│ ├── mergeSort([3])
│ └── mergeSort([9])
└── mergeSort([82,10])
├── mergeSort([82])
└── mergeSort([10])
Levels: log₂(7) ≈ 3 levels
Work per level: n = 7 comparisons
Total: ~3 × 7 = 21 operations = O(n log n)Merge Sort vs Quick Sort vs Heap Sort
Merge Sort
O(n log n) always, stable, O(n) space. Best for: linked lists, external sorting (data too big for RAM), stability required. Interview favorite for predictability.
Quick Sort
O(n log n) average, O(n²) worst case, in-place (O(log n) stack space), not stable. Fastest in practice due to cache efficiency, but risky on sorted data without good pivot selection.
Heap Sort
O(n log n) always, in-place (O(1) space), not stable. Best when memory is very constrained. Poor cache performance makes it slower than merge/quick in practice.
TimSort (JS/Python built-in)
Hybrid merge + insertion sort. O(n log n) worst, O(n) for nearly-sorted input. The actual algorithm used in JavaScript V8, Python, and Java Arrays.sort for objects.
Interview Applications — The Merge Step Pattern
The merge step from merge sort is a standalone pattern that appears in several high-frequency interview problems. Recognizing it is key to solving them efficiently.
function mergeSortedArrays(nums1, m, nums2, n) {
// Merge from the back to avoid shifting elements
let i = m - 1; // last valid element in nums1
let j = n - 1; // last element in nums2
let k = m + n - 1; // last position in result
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
// Copy remaining nums2 elements (nums1 elements are already in place)
while (j >= 0) nums1[k--] = nums2[j--];
return nums1;
}
mergeSortedArrays([1,2,3,0,0,0], 3, [2,5,6], 3);
// → [1,2,2,3,5,6]
// Time: O(m+n), Space: O(1)// An inversion is a pair (i, j) where i < j but arr[i] > arr[j]
// Classic divide-and-conquer interview problem
function countInversions(arr) {
if (arr.length <= 1) return { sorted: arr, count: 0 };
const mid = Math.floor(arr.length / 2);
const { sorted: left, count: leftCount } = countInversions(arr.slice(0, mid));
const { sorted: right, count: rightCount } = countInversions(arr.slice(mid));
let count = leftCount + rightCount;
const merged = [];
let l = 0, r = 0;
while (l < left.length && r < right.length) {
if (left[l] <= right[r]) {
merged.push(left[l++]);
} else {
// Every remaining element in left is > right[r]
count += left.length - l; // Count inversions
merged.push(right[r++]);
}
}
return {
sorted: merged.concat(left.slice(l)).concat(right.slice(r)),
count,
};
}
countInversions([3, 1, 2]).count; // → 2 (pairs: (3,1), (3,2))// Merge sort is preferred for linked lists because:
// 1. No random access needed (arrays can use quick sort with index tricks)
// 2. O(1) extra space for linked list merge (just pointer manipulation)
function sortList(head) {
if (!head || !head.next) return head;
// Find middle using slow/fast pointers
let slow = head, fast = head.next;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// Split the list in half
const mid = slow.next;
slow.next = null; // Cut the list
const left = sortList(head);
const right = sortList(mid);
return mergeLists(left, right);
}
function mergeLists(l1, l2) {
const dummy = { next: null };
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;
return dummy.next;
}
// Time: O(n log n), Space: O(log n) call stackSorting Stability — Why It Matters
Stability is critical for multi-key sorting
const employees = [
{ name: 'Alice', dept: 'Engineering' },
{ name: 'Bob', dept: 'Marketing' },
{ name: 'Carol', dept: 'Engineering' },
{ name: 'Dave', dept: 'Marketing' },
];
// First sort by name (already alphabetical here)
// Then sort by department — stable sort preserves name order within dept
employees.sort((a, b) => a.dept.localeCompare(b.dept));
// Result (stable): Engineering: [Alice, Carol], Marketing: [Bob, Dave]
// Unstable sort might give: Engineering: [Carol, Alice] — relative order lost
// JavaScript's Array.prototype.sort() is stable in all modern engines (V8, SpiderMonkey)
// This is guaranteed by spec since ECMAScript 2019External Sorting — Real-World Merge Sort
Merge sort is the foundation of external sorting — sorting datasets too large to fit in RAM. The algorithm writes sorted chunks to disk, then merges them. This is how databases handle ORDER BY on large tables and how Hadoop sorts terabytes of data.
import heapq
import tempfile
import os
def external_sort(input_file, output_file, chunk_size=1000):
"""
Sort a large file that doesn't fit in memory.
1. Read chunks, sort each chunk, write to temp files
2. Merge-sort the temp files using a min-heap
"""
temp_files = []
# Phase 1: Create sorted runs
with open(input_file) as f:
while True:
chunk = [int(f.readline()) for _ in range(chunk_size) if not f.readline() == '']
if not chunk:
break
chunk.sort()
tmp = tempfile.NamedTemporaryFile(mode='w', delete=False)
tmp.write('\n'.join(map(str, chunk)))
temp_files.append(tmp.name)
# Phase 2: Merge sorted runs using a min-heap
readers = [open(f) for f in temp_files]
heap = []
for i, reader in enumerate(readers):
line = reader.readline()
if line:
heapq.heappush(heap, (int(line), i))
with open(output_file, 'w') as out:
while heap:
val, i = heapq.heappop(heap)
out.write(str(val) + '\n')
line = readers[i].readline()
if line:
heapq.heappush(heap, (int(line), i))
# Cleanup
for r, f in zip(readers, temp_files):
r.close()
os.unlink(f)