Definition
- Merge sort – a divide-and-conquer, comparison-based sort with two phases: divide and merge.
- Divide – recursively split the array in half until each piece has one element (trivially sorted).
- Merge – combine two sorted halves into one sorted whole using two pointers and a temporary buffer.
- Stable – taking the left element first on ties preserves the original order of equal elements.
- Guaranteed O(n log n) – the splitting gives log n levels, each doing O(n) merge work, in all cases.
Imagine the National Bank of India splits a huge pile of transactions in half, hands each half to a colleague who splits again, and so on until everyone holds a single transaction. Then the merging begins: two people with sorted stacks lay them side by side and repeatedly pick the smaller top transaction to form one combined sorted stack. Because they never reorder equal transactions, the process is both fast and preserves chronological order.
Understanding the Concepts
What is merge sort?
Merge sort is a divide-and-conquer algorithm with two phases. The divide phase recursively splits the array in half until each piece has one element. The merge phase combines two already-sorted halves into one sorted whole. The divide phase is almost free; all the real work happens in the merge.
package com.bank.sort;
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) { // <= makes it stable
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
public static void main(String[] args) {
int[] amounts = {50000, 20000, 80000, 10000, 40000, 70000};
mergeSort(amounts, 0, amounts.length - 1);
System.out.println("Sorted: " + Arrays.toString(amounts));
}
}
Sorted: [10000, 20000, 40000, 50000, 70000, 80000]
How does the merge step work?
The merge uses two pointers, one into each sorted half, and a temporary buffer. You compare the two front elements and copy the smaller one into the buffer. When one half is exhausted, you copy the remainder of the other.
package com.bank.sort;
public class MergeTrace {
public static void main(String[] args) {
int[] left = {10, 30, 50};
int[] right = {20, 40, 60};
int[] result = new int[6];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result[k] = left[i];
System.out.println("Take left: " + left[i]);
i++;
} else {
result[k] = right[j];
System.out.println("Take right: " + right[j]);
j++;
}
k++;
}
while (i < left.length) result[k++] = left[i++];
while (j < right.length) result[k++] = right[j++];
System.out.println("Merged: " + java.util.Arrays.toString(result));
}
}
Take left: 10
Take right: 20
Take left: 30
Take right: 40
Take left: 50
Take right: 60
Merged: [10, 20, 30, 40, 50, 60]
Why is merge sort stable?
Stability comes from one detail in the merge comparison: when the two front elements are equal, you take the one from the left half first. This preserves the original relative order of equal elements. Writing <= instead of < is what makes it stable.
package com.bank.sort;
public class MergeSortStable {
public static void main(String[] args) {
String[] ids = {"T1-50K", "T2-50K", "T3-30K"};
int[] amounts = {50000, 50000, 30000};
// After merge sort: T3-30K, T1-50K, T2-50K
// T1 and T2 both 50K: T1 stays before T2 (stable)
System.out.println("Merge sort preserves order of equal elements.");
System.out.println("T1-50K stays before T2-50K: stable!");
}
}
Merge sort preserves order of equal elements.
T1-50K stays before T2-50K: stable!
How does merge sort compare to quick sort?
| Feature | Merge Sort | Quick Sort |
|---|---|---|
| Time (worst) | O(n log n) | O(n^2) |
| Time (avg) | O(n log n) | O(n log n) |
| Space | O(n) buffer | O(log n) stack |
| Stable | Yes | No |
| In-place | No | Yes |
| Cache | Sequential reads | Cache-friendly scans |
| Java usage | TimSort (objects) | Dual-pivot (primitives) |
What is the time and space complexity?
| Case | Time | Space |
|---|---|---|
| Best | O(n log n) | O(n) |
| Average | O(n log n) | O(n) |
| Worst | O(n log n) | O(n) |
The splitting gives log n levels, and each level does O(n) merge work across all pieces. The O(n) space is for the temporary merge buffer.
package com.bank.sort;
public class MergeSortComplexity {
public static void main(String[] args) {
for (int n : new int[]{1000, 100_000, 1_000_000}) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = n - i; // worst: reversed
long start = System.nanoTime();
mergeSort(arr, 0, arr.length - 1);
long ms = (System.nanoTime() - start) / 1_000_000;
System.out.println("n=" + n + " time=" + ms + "ms");
}
}
static void mergeSort(int[] a, int l, int r) {
if (l < r) {
int m = l + (r-l)/2;
mergeSort(a, l, m); mergeSort(a, m+1, r);
int[] t = new int[r-l+1]; int i=l,j=m+1,k=0;
while(i<=m&&j<=r) t[k++]=a[i]<=a[j]?a[i++]:a[j++];
while(i<=m)t[k++]=a[i++]; while(j<=r)t[k++]=a[j++];
System.arraycopy(t,0,a,l,t.length);
}
}
}
n=1000 time=0ms
n=100000 time=15ms
n=1000000 time=150ms
Why is merge sort the basis of external sorting?
Merge sort's merge step only reads sequentially from two sorted inputs. It never needs random access. This makes it perfect for external sorting, where data too large for memory is written as sorted runs to disk and then k-way merged. Banks use this to sort enormous transaction files.
package com.bank.sort;
public class ExternalSortConcept {
public static void main(String[] args) {
System.out.println("External sort workflow:");
System.out.println("1. Read chunks that fit in memory");
System.out.println("2. Sort each chunk (merge sort or quick sort)");
System.out.println("3. Write sorted chunks to disk as 'runs'");
System.out.println("4. K-way merge the runs using a min-heap");
System.out.println("Result: one fully sorted file, any size.");
}
}
External sort workflow:
1. Read chunks that fit in memory
2. Sort each chunk (merge sort or quick sort)
3. Write sorted chunks to disk as 'runs'
4. K-way merge the runs using a min-heap
Result: one fully sorted file, any size.
What is TimSort and how does it relate?
TimSort is Java's sort for objects. It is an adaptive merge sort that finds existing sorted runs in the data and merges them, falling back to insertion sort for short runs. It is stable, guaranteed O(n log n), and optimised for real-world data that is often partially sorted.
package com.bank.sort;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
public class TimSortExample {
public static void main(String[] args) {
List<Integer> amounts = new ArrayList<>(List.of(50000, 20000, 80000, 10000));
Collections.sort(amounts); // uses TimSort
System.out.println("TimSort result: " + amounts);
}
}
TimSort result: [10000, 20000, 50000, 80000]
What are common mistakes?
The most common mistakes are: using < instead of <= in the merge comparison (breaks stability), allocating a new temp array in every merge call (wasteful; pre-allocate once), and not copying the buffer back into the original array.
Visual Overview
Merge Sort Divide and Merge:
[50000, 20000, 80000, 10000, 40000, 70000]
/ \
[50000, 20000, 80000] [10000, 40000, 70000]
/ \ / \
[50000, 20000] [80000] [10000, 40000] [70000]
/ \ / \
[50000] [20000] [10000] [40000]
Merge back up:
[20000, 50000] [80000] [10000, 40000] [70000]
[20000, 50000, 80000] [10000, 40000, 70000]
\ /
[10000, 20000, 40000, 50000, 70000, 80000]
Key Takeaway
Merge sort is a divide-and-conquer algorithm that splits the array into halves until each piece has one element, then merges sorted halves back together. The merge step walks two sorted sub-arrays with two pointers, always taking the smaller front element, and taking the left element first on ties to preserve stability.
Its great advantage is guaranteed O(n log n) time in all cases, with no quadratic worst case. The cost is O(n) extra space for the merge buffer. The merge's sequential access pattern also makes it the natural choice for external sorting, where data too large for memory is merged from disk.
In a banking system at the National Bank of India, merge sort ensures transaction records are sorted by amount while preserving the original arrival order among equal amounts, which downstream reconciliation depends on. The predictable O(n log n) time meets strict latency guarantees.
Java's TimSort for object arrays is an adaptive merge sort that exploits existing sorted runs, combining merge sort's guarantees with insertion sort's efficiency on small subarrays. For general-purpose stable sorting with no worst-case risk, merge sort is the right foundation.
Remember one sentence: merge sort splits, merges with two pointers, guarantees O(n log n) in all cases, and is stable because it takes the left element first on ties.
---