Merge Sort
Split in half, sort each half recursively, merge the sorted halves. Always O(n log n) regardless of input. Stable (preserves order of equal elements). Needs O(n) extra space for merging.
How It Works
Merge sort splits the array into halves, recursively sorts each half, and then merges the two sorted runs with a two-pointer pass that repeatedly takes the smaller front element. The merge is where all real work happens: combining two sorted lists of total length n takes exactly O(n) comparisons and copies.
The recursion has log n levels and each level merges n total elements, so the running time is O(n log n) for every input — no bad cases, unlike quick sort. Taking from the left run on ties makes the sort stable, which is why Timsort and other library sorts build on merging. The costs are O(n) auxiliary space for the merge buffer and less cache-friendly access than quick sort. Merge sort also adapts naturally to linked lists (no random access needed, O(1) extra space) and underlies divide-and-conquer counting problems like counting inversions.
Step-by-Step Visualization
Code
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);
}
static int[] merge(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
result[k++] = a[i] <= b[j] ? a[i++] : b[j++];
while (i < a.length) result[k++] = a[i++];
while (j < b.length) result[k++] = b[j++];
return result;
}Tips & Gotchas
Practice Problems
- 1Sort List
- 2Merge k Sorted Lists
- 3Count of Smaller Numbers After Self
- 4Reverse Pairs
About the Comparison Sorts Pattern
Sort by comparing pairs of elements. No comparison sort can do better than O(n log n) in the worst case — this is a proven lower bound. The three main ones differ in stability, space, and constant factors.
Sorting unlocks binary search, two-pointer, and greedy. Always ask: can I sort first? Custom comparators solve tricky ordering problems. Know QuickSelect for O(n) expected Kth element.
Common Sorting Interview Problems
- Sort Colors
- Kth Largest Element
- Merge Intervals
- Largest Number
- Sort List
- Meeting Rooms
Frequently Asked Questions
When should I reach for merge sort over quick sort?
When stability is required, when a guaranteed O(n log n) worst case matters, or when sorting linked lists, where merge sort needs no random access and no extra buffer. Quick sort generally wins on raw speed for in-memory arrays of primitives due to cache locality and in-place partitioning.
Why does merge sort appear inside problems like Count of Smaller Numbers After Self?
The merge step compares elements across the two halves in sorted order, which is the perfect moment to count cross-half relationships — every time a right-half element is taken first, it is smaller than all remaining left-half elements. Piggybacking these counts on the merge keeps the whole computation O(n log n) instead of the O(n^2) pairwise check.