Merge Sort
What Is Merge Sort?
Merge sort is a divide-and-conquer algorithm. It recursively splits the array into halves until single-element subarrays remain (a single element is always sorted), then merges the sorted halves back together into a single sorted array.
Divide phase: [38, 27, 43, 3, 9, 82, 10]
/ \
[38, 27, 43, 3] [9, 82, 10]
/ \ / \
[38, 27] [43, 3] [9, 82] [10]
/ \ / \ / \
[38] [27] [43] [3] [9] [82]
Merge phase (sorted halves joined):
[38] [27] [43] [3] [9] [82]
\ / \ / \ /
[27,38] [3,43] [9,82]
\ / /
[3, 27, 38, 43] [9, 10, 82]
\ /
[3, 9, 10, 27, 38, 43, 82]
The key operation is the merge: given two sorted arrays, produce one sorted array by comparing their front elements and taking the smaller one at each step.
The Merge Operation
The heart of merge sort — merging two sorted subarrays into one sorted array:
Left: [3, 27, 38, 43]
Right: [9, 10, 82]
i j
Compare arr[i]=3 vs arr[j]=9: 3 < 9 → take 3, i++ output=[3]
Compare arr[i]=27 vs arr[j]=9: 27 > 9 → take 9, j++ output=[3,9]
Compare arr[i]=27 vs arr[j]=10: 27 > 10→ take 10, j++ output=[3,9,10]
Compare arr[i]=27 vs arr[j]=82: 27 < 82→ take 27, i++ output=[3,9,10,27]
Compare arr[i]=38 vs arr[j]=82: 38 < 82→ take 38, i++ output=[3,9,10,27,38]
Compare arr[i]=43 vs arr[j]=82: 43 < 82→ take 43, i++ output=[3,9,10,27,38,43]
Left exhausted — append remaining right: [82]
Final: [3, 9, 10, 27, 38, 43, 82] ✓
Stability rule: when arr[i] == arr[j], take from LEFT first (use <=)
This preserves the original relative order of equal elements.
Recursive (Top-Down) Merge Sort
1import java.util.Arrays;
2
3public class MergeSort {
4
5 public static void mergeSort(int[] arr, int lo, int hi) {
6 if (lo >= hi) return; // Base case: single element — already sorted
7
8 int mid = lo + (hi - lo) / 2;
9
10 mergeSort(arr, lo, mid); // Sort left half
11 mergeSort(arr, mid + 1, hi); // Sort right half
12 merge(arr, lo, mid, hi); // Merge sorted halves
13 }
14
15 private static void merge(int[] arr, int lo, int mid, int hi) {
16 // Copy both halves into a temporary array
17 int[] temp = Arrays.copyOfRange(arr, lo, hi + 1);
18
19 int i = 0; // Pointer into left half of temp
20 int j = mid - lo + 1; // Pointer into right half of temp
21 int k = lo; // Pointer into original arr (output)
22
23 int leftEnd = mid - lo; // Last index of left half in temp
24 int rightEnd = hi - lo; // Last index of right half in temp
25
26 while (i <= leftEnd && j <= rightEnd) {
27 if (temp[i] <= temp[j]) { // <= ensures stability (left before right on tie)
28 arr[k++] = temp[i++];
29 } else {
30 arr[k++] = temp[j++];
31 }
32 }
33
34 // Copy remaining elements from either half
35 while (i <= leftEnd) arr[k++] = temp[i++];
36 while (j <= rightEnd) arr[k++] = temp[j++];
37 }
38
39 public static void sort(int[] arr) {
40 if (arr.length > 1) mergeSort(arr, 0, arr.length - 1);
41 }
42
43 public static void main(String[] args) {
44 int[] arr1 = {38, 27, 43, 3, 9, 82, 10};
45 sort(arr1);
46 System.out.println(Arrays.toString(arr1));
47 // [3, 9, 10, 27, 38, 43, 82]
48
49 int[] arr2 = {5, 2, 4, 6, 1, 3};
50 sort(arr2);
51 System.out.println(Arrays.toString(arr2));
52 // [1, 2, 3, 4, 5, 6]
53
54 int[] single = {42};
55 sort(single);
56 System.out.println(Arrays.toString(single)); // [42]
57
58 int[] two = {2, 1};
59 sort(two);
60 System.out.println(Arrays.toString(two)); // [1, 2]
61 }
62}Output:
[3, 9, 10, 27, 38, 43, 82]
[1, 2, 3, 4, 5, 6]
[42]
[1, 2]
Complete Dry Run: [5, 2, 4, 6, 1, 3]
DIVIDE:
mergeSort([5,2,4,6,1,3], 0, 5)
mid=2
mergeSort([5,2,4], 0, 2)
mid=1
mergeSort([5,2], 0, 1)
mid=0
mergeSort([5], 0, 0) → base case
mergeSort([2], 1, 1) → base case
merge([5],[2]) → [2,5]
mergeSort([4], 2, 2) → base case
merge([2,5],[4]) → [2,4,5]
mergeSort([6,1,3], 3, 5)
mid=4
mergeSort([6,1], 3, 4)
mid=3
mergeSort([6], 3, 3) → base case
mergeSort([1], 4, 4) → base case
merge([6],[1]) → [1,6]
mergeSort([3], 5, 5) → base case
merge([1,6],[3]) → [1,3,6]
merge([2,4,5],[1,3,6]) → [1,2,3,4,5,6]
MERGE trace for final step ([2,4,5] and [1,3,6]):
i=0(2) j=0(1): 2>1 → take 1, j=1 output=[1]
i=0(2) j=1(3): 2<3 → take 2, i=1 output=[1,2]
i=1(4) j=1(3): 4>3 → take 3, j=2 output=[1,2,3]
i=1(4) j=2(6): 4<6 → take 4, i=2 output=[1,2,3,4]
i=2(5) j=2(6): 5<6 → take 5, i=3 output=[1,2,3,4,5]
Left exhausted, append right [6] output=[1,2,3,4,5,6] ✓
Why Merge Sort Is Stable
During the merge, when left[i] == right[j], the code uses <= — taking from the LEFT half first:
if temp[i] <= temp[j]: ← <= means left wins on tie
arr[k] = temp[i]
Example: Left=[A(3), C(3)] Right=[B(3)] (sorting by number)
Compare A(3) vs B(3): 3 <= 3 → take A from left
Compare C(3) vs B(3): 3 <= 3 → take C from left
Append remaining B from right
Result: [A(3), C(3), B(3)]
A comes from original index before C, C before B.
All three were at different positions originally — the merge
takes left before right on ties, preserving position order.
UNSTABLE version (using < instead of <=):
Compare A(3) vs B(3): 3 < 3? No → take B from right first
Result: [B(3), A(3), C(3)] ← B jumped ahead of A — UNSTABLE!
One character makes merge sort stable or not: <= is stable, < is unstable.
Iterative (Bottom-Up) Merge Sort
No recursion — merges subarrays of increasing sizes iteratively. Avoids stack overhead and is easier to implement for external sorting.
1import java.util.Arrays;
2
3public class BottomUpMergeSort {
4
5 public static void bottomUpMergeSort(int[] arr) {
6 int n = arr.length;
7
8 // size: current subarray size being merged (1, 2, 4, 8, ...)
9 for (int size = 1; size < n; size *= 2) {
10 // lo: starting index of each pair of subarrays to merge
11 for (int lo = 0; lo < n - size; lo += 2 * size) {
12 int mid = lo + size - 1;
13 int hi = Math.min(lo + 2 * size - 1, n - 1);
14 merge(arr, lo, mid, hi);
15 }
16 }
17 }
18
19 private static void merge(int[] arr, int lo, int mid, int hi) {
20 int[] temp = Arrays.copyOfRange(arr, lo, hi + 1);
21 int i = 0, j = mid - lo + 1, k = lo;
22 int leftEnd = mid - lo, rightEnd = hi - lo;
23
24 while (i <= leftEnd && j <= rightEnd) {
25 if (temp[i] <= temp[j]) arr[k++] = temp[i++];
26 else arr[k++] = temp[j++];
27 }
28 while (i <= leftEnd) arr[k++] = temp[i++];
29 while (j <= rightEnd) arr[k++] = temp[j++];
30 }
31
32 public static void main(String[] args) {
33 int[] arr = {5, 2, 4, 6, 1, 3};
34 bottomUpMergeSort(arr);
35 System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6]
36
37 int[] arr2 = {38, 27, 43, 3, 9, 82, 10};
38 bottomUpMergeSort(arr2);
39 System.out.println(Arrays.toString(arr2)); // [3, 9, 10, 27, 38, 43, 82]
40 }
41}Output:
[1, 2, 3, 4, 5, 6]
[3, 9, 10, 27, 38, 43, 82]
Bottom-Up Pass Trace: [5, 2, 4, 6, 1, 3]
n=6
Pass 1 (size=1): merge pairs of size 1
lo=0: merge [5],[2] → [2,5] arr=[2,5,4,6,1,3]
lo=2: merge [4],[6] → [4,6] arr=[2,5,4,6,1,3] → [2,5,4,6,1,3]
wait: arr=[2,5,4,6,1,3] after merge at lo=2: arr=[2,5,4,6,1,3]
lo=4: merge [1],[3] → [1,3] arr=[2,5,4,6,1,3] → [2,5,4,6,1,3]
After pass 1: [2,5, 4,6, 1,3] (pairs sorted)
Pass 2 (size=2): merge pairs of size 2
lo=0: merge [2,5],[4,6] → [2,4,5,6] arr=[2,4,5,6,1,3]
lo=4: n-size=4, lo=4 not < 4 → skip... wait lo=4 < n-size=6-2=4? No.
Actually: lo=4 < 4? No → only one merge at lo=0
But we also merge lo=4 if lo < n-size=4... 4 < 4 is false.
Remaining [1,3] stays as is since no pair exists.
After pass 2: [2,4,5,6, 1,3]
Pass 3 (size=4): merge pairs of size 4
lo=0: mid=3, hi=min(7,5)=5
merge [2,4,5,6],[1,3] → [1,2,3,4,5,6]
After pass 3: [1,2,3,4,5,6] ✓
Application: Count Inversions
Problem: Count the number of inversions in an array — pairs (i, j) where i < j but arr[i] > arr[j].
Merge sort insight: During the merge step, whenever a right-half element is taken before remaining left-half elements, each remaining left-half element forms an inversion with this right-half element.
Merge [3, 5, 7] and [2, 4, 6]:
Compare 3 vs 2: 3 > 2 → take 2.
Remaining in left: [3, 5, 7] — 3 inversions (3>2, 5>2, 7>2)
inversions += 3 (size of remaining left)
Compare 3 vs 4: 3 < 4 → take 3. No inversions.
Compare 5 vs 4: 5 > 4 → take 4.
Remaining in left: [5, 7] — 2 inversions (5>4, 7>4)
inversions += 2
Compare 5 vs 6: 5 < 6 → take 5. No inversions.
Compare 7 vs 6: 7 > 6 → take 6.
Remaining in left: [7] — 1 inversion (7>6)
inversions += 1
7 remains — append.
Total inversions: 3+2+1 = 6
1public class CountInversions {
2
3 private static long count = 0;
4
5 public static long countInversions(int[] arr) {
6 count = 0;
7 mergeSortCount(arr, 0, arr.length - 1);
8 return count;
9 }
10
11 private static void mergeSortCount(int[] arr, int lo, int hi) {
12 if (lo >= hi) return;
13 int mid = lo + (hi - lo) / 2;
14 mergeSortCount(arr, lo, mid);
15 mergeSortCount(arr, mid + 1, hi);
16 mergeCount(arr, lo, mid, hi);
17 }
18
19 private static void mergeCount(int[] arr, int lo, int mid, int hi) {
20 int[] temp = java.util.Arrays.copyOfRange(arr, lo, hi + 1);
21 int i = 0, j = mid - lo + 1, k = lo;
22 int leftEnd = mid - lo, rightEnd = hi - lo;
23
24 while (i <= leftEnd && j <= rightEnd) {
25 if (temp[i] <= temp[j]) {
26 arr[k++] = temp[i++];
27 } else {
28 // All elements temp[i..leftEnd] are greater than temp[j]
29 count += (leftEnd - i + 1); // Count inversions
30 arr[k++] = temp[j++];
31 }
32 }
33 while (i <= leftEnd) arr[k++] = temp[i++];
34 while (j <= rightEnd) arr[k++] = temp[j++];
35 }
36
37 public static void main(String[] args) {
38 System.out.println(countInversions(new int[]{2, 4, 1, 3, 5})); // 3
39 System.out.println(countInversions(new int[]{5, 4, 3, 2, 1})); // 10
40 System.out.println(countInversions(new int[]{1, 2, 3, 4, 5})); // 0
41 System.out.println(countInversions(new int[]{1, 20, 6, 4, 5}})); // 5
42 }
43}Output:
3
10
0
5
Complexity Analysis
Time Complexity
Recurrence: T(n) = 2T(n/2) + O(n) Split into 2 subproblems of size n/2 → 2T(n/2) Merge two halves costs O(n) → +O(n) By Master Theorem (case 2): a=2, b=2, f(n)=n, n^log_b(a) = n^1 = n f(n) = Θ(n^log_b(a)) → T(n) = O(n log n) Recursion tree: Level 0: 1 merge of size n → n comparisons Level 1: 2 merges of size n/2 → n comparisons Level 2: 4 merges of size n/4 → n comparisons ... Level log n: n merges of size 1 → n comparisons Total: n × log n = O(n log n) SAME in best, average, and worst case — merge sort is not input-sensitive.
Space Complexity
Auxiliary array: O(n) — needed for the merge step Recursion stack: O(log n) — depth of recursion tree Total: O(n) Bottom-up merge sort: No recursion stack — O(1) stack space Still O(n) for the auxiliary array Total: O(n) Cannot avoid the O(n) auxiliary array for efficient merging. In-place merge is possible but O(n log n) extra operations — impractical.
Merge Sort vs Quick Sort
Property Merge Sort Quick Sort ────────────────────────────────────────────────────────────────── Time (best) O(n log n) O(n log n) Time (average) O(n log n) O(n log n) Time (worst) O(n log n) ← WINNER O(n²) — bad pivot Space O(n) — aux array O(log n) — stack only Stable ✓ Yes ← WINNER ✗ No Adaptive ✗ No Partial Cache behaviour Good Better (in-place) External sort ✓ Yes ← WINNER ✗ No Used in practice TimSort IntroSort When to choose Merge Sort: ✓ Stability required (sorting objects with equal keys) ✓ Linked list sorting (no random access needed for merge) ✓ External sorting (data too large for RAM) ✓ Guaranteed O(n log n) needed (cannot risk O(n²) worst case) When to choose Quick Sort: ✓ In-place required (O(1) extra space) ✓ Cache performance critical (array-based, in-place) ✓ Average-case speed maximised ✓ No stability needed
Complexity Summary
| Variant | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Top-down merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ Yes |
| Bottom-up merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ Yes |
| Count inversions | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ Yes |
| External merge sort | O(n log n) | O(n log n) | O(n log n) | O(k) disk | ✓ Yes |
Common Mistakes
Using < instead of <= in the merge comparison. if temp[i] < temp[j] makes the sort unstable — right-half elements are taken first on ties. Always use <= (left before right on equal) to maintain stability. This is the single most common merge sort mistake.
Not correctly computing mid for the bottom-up variant. In bottom-up, mid = lo + size - 1 and hi = min(lo + 2*size - 1, n-1). A common error is setting hi = lo + 2*size - 1 without the min clamp — this causes out-of-bounds access when the last group does not have a full second half.
Forgetting that the counting inversions logic requires leftEnd - i + 1 not leftEnd - i. When a right element is taken, the remaining left elements (indices i through leftEnd inclusive) all form inversions. The count is leftEnd - i + 1. Using leftEnd - i misses the element at index i itself.
Allocating a new auxiliary array inside every merge call. This is correct but allocates O(n log n) total memory across all merge calls (each level allocates O(n)). The optimisation is to allocate one auxiliary array of size n upfront and pass it to all merge calls — reducing total allocation to O(n).
Interview Questions
Q: Why is merge sort preferred over quick sort for linked lists?
Merge sort's split operation (finding mid, splitting) is O(n/2) for linked lists — find the midpoint using slow/fast pointers. Its merge operation is O(n) using pointer relinking — no copying needed. The overall O(n log n) is maintained. Quick sort's partition step needs to compare elements and swap, which on a linked list requires O(n) per swap (to find the position). Merge sort is the natural sort for linked lists — it only needs to traverse and relink, never random-access.
Q: What is an external merge sort and why is it used?
External merge sort handles data too large to fit in RAM. Phase 1 (sort runs): read chunks of data that fit in RAM, sort each chunk in memory, write sorted runs to disk. Phase 2 (merge runs): use a k-way merge (one pointer per sorted file) with a min-heap to merge all sorted runs in one pass. The heap always gives the global minimum, writing it to the output file. Total: O(N log N) comparisons, O(N) disk reads/writes. Database systems (MySQL, PostgreSQL) and MapReduce use this pattern.
Q: What is the recurrence relation for merge sort and how do you solve it?
T(n) = 2T(n/2) + O(n). This is solved by the Master Theorem: a=2 (two subproblems), b=2 (each half the size), f(n)=n (merge cost). Since f(n) = n = n^(log₂2) = n^1, we are in case 2 of the Master Theorem: T(n) = O(n^log_b(a) × log n) = O(n log n).
FAQs
Can merge sort be done in O(1) extra space?
In-place merge sort exists but is complex and has large constant factors. The in-place merge step (rotating the unsorted middle) takes O(n) time but with O(n log n) total operations, making the overall algorithm O(n log² n). This is worse than the standard O(n log n) with O(n) space. In practice, O(1) in-place merge sort is not used — quick sort or heapsort is chosen instead when in-place is required.
Why does merge sort have better cache behaviour than expected despite O(n) memory?
During each merge, the read pattern is sequential (reading from left and right halves of the temp array) and the write is sequential (writing to the output array). Sequential memory access is cache-friendly. While the auxiliary array adds memory usage, the access patterns are regular — no random jumps. QuickSort, being in-place, may seem more cache-friendly, but its partition step can cause cache misses with adversarial pivots.
Is TimSort merge sort?
TimSort is based on merge sort. It identifies natural sorted runs in the input, extends short runs to a minimum length using insertion sort, then merges runs using a modified merge sort with galloping mode (exponential search for long sequences of elements from one side). The key innovation is exploiting existing order in real-world data — typical inputs are partially sorted, and TimSort turns this into an advantage, achieving O(n) for already-sorted input while maintaining O(n log n) worst case.
Summary
Merge sort is the divide-and-conquer O(n log n) sort with a guaranteed stable outcome.
Algorithm in three steps:
- ›Split the array in half recursively until single-element subarrays
- ›Merge sorted halves using two-pointer merge (always O(n) per level)
- ›Repeat until the full array is merged
Stability — one character matters:
- ›
<=in the merge comparison → stable (left before right on ties) - ›
<in the merge comparison → unstable
Two variants:
- ›Top-down (recursive): natural, log n stack depth, O(n) auxiliary
- ›Bottom-up (iterative): no stack, merge size=1,2,4,8... — same O(n log n), O(n) auxiliary
Inversion counting: piggyback on merge sort — when right element is taken, count leftEnd - i + 1 inversions. O(n log n) total.
Comparison with quick sort:
- ›Merge sort wins: stability, guaranteed O(n log n), linked lists, external sort
- ›Quick sort wins: in-place (O(log n) space), better cache behaviour in practice
In the next topic, you will explore Quick Sort — the in-place O(n log n) average-case sort that sacrifices stability for dramatically better space efficiency and cache performance.
What is the time complexity of merge sort in all cases?