These are the notes for DSA episode 17, the second episode of the sorting block. Episode 16 ended with a problem: on two lakh random numbers, bubble, selection and insertion sort all hit the time limit, because they are O(n²). Here we invent merge sort, a divide and conquer sort that is O(n log n) in every case, and then use it to solve a classic interview problem, counting inversions, by adding one line to the merge. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
Exam results day. The office has a pile of 40 jumbled answer sheets that must be sorted by roll number. One person alone is slow (that is what the simple sorts do). So the head clerk works like this:
| In the exam office | In merge sort |
|---|---|
| Split the pile in half, hand each half to a helper; they split again, and again | Divide: split the array into two halves, recursively |
| A helper holding one sheet has nothing to do: it is already sorted | Base case: a part of size 0 or 1 is sorted |
| A helper gets two sorted piles, compares the two top sheets, takes the smaller one, repeats | Combine: merge two sorted halves |
Splitting the work and then combining the results is called divide and conquer.
Problem statements
Problem 1, sorting. Sort an array of up to 2 × 10⁵ integers in non-decreasing order, fast: [5, 1, 4, 2, 8] → [1, 2, 4, 5, 8].
Problem 2, counting inversions. An inversion is a pair of indices i < j with a[i] > a[j] (a bigger value before a smaller one). Count them.
[5, 1, 4, 2, 8]→ (5,1), (5,4), (5,2), (4,2) → 4- a sorted array → 0; a reversed array of length n → n(n - 1)/2 (every pair)
[3, 3, 1, 3]→ 2 (each 3 before the 1; equal values are not inversions)- Constraints: n up to 2 × 10⁵, so the answer can be about 2 × 10¹⁰: it needs a
long.
Real-life meaning: Asha and Ravi rank the same five movies. Write Ravi's scores in Asha's order. Each pair of movies they rank differently is an inversion, so the count measures how much their tastes disagree (this is the idea behind the Kendall tau distance used by ranking and recommendation systems). It is also exactly the number of swaps bubble sort makes (episode 16's homework answer: 4).
The merge: two sorted piles into one
Pointer i walks the left pile, j the right pile. Always take the smaller top; when one pile is empty, copy the rest of the other.
| Step | Left top | Right top | Take | Merged so far |
|---|---|---|---|---|
| 1 | 1 | 2 | 1 (left) | [1] |
| 2 | 4 | 2 | 2 (right) | [1, 2] |
| 3 | 4 | 8 | 4 (left) | [1, 2, 4] |
| 4 | 5 | 8 | 5 (left) | [1, 2, 4, 5] |
| 5 | (empty) | 8 | copy leftovers | [1, 2, 4, 5, 8] |
Each step places one element, so merging n elements is O(n).
Merge sort
On [5, 1, 4, 2, 8]:
split: [5, 1, 4] [2, 8]
split: [5, 1] [4] [2] [8]
size 1: [5] [1] [4] [2] [8] ← already sorted
merge: [1, 5] [4] [2, 8]
merge: [1, 4, 5] [2, 8]
merge: [1, 2, 4, 5, 8]
We use half-open ranges [lo, hi): lo is included, hi is not (like substring and most Java APIs). The part has hi - lo elements.
import java.util.*;
public class Main {
static void mergeSort(int[] a) {
sort(a, new int[a.length], 0, a.length);
}
static void sort(int[] a, int[] tmp, int lo, int hi) {
if (hi - lo <= 1) return;
int mid = (lo + hi) / 2;
sort(a, tmp, lo, mid);
sort(a, tmp, mid, hi);
merge(a, tmp, lo, mid, hi);
}
static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
int i = lo, j = mid, k = lo;
while (i < mid && j < hi)
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
for (k = lo; k < hi; k++) a[k] = tmp[k];
}
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 8};
mergeSort(a);
System.out.println(Arrays.toString(a));
int[] e = {};
mergeSort(e);
System.out.println(Arrays.toString(e));
int[] d = {3, 3, 1, 3, 7};
mergeSort(d);
System.out.println(Arrays.toString(d));
}
}
Output:
[1, 2, 4, 5, 8]
[]
[1, 3, 3, 3, 7]
Notes on the code:
a[i] <= a[j]: on a tie the left element goes first, so equal values keep their order: merge sort is stable.- One temporary array
tmpis created once, inmergeSort, and shared by every merge (allocating a new array in every call also works, but is slower). (lo + hi) / 2is safe here; for ranges near 2³¹ writelo + (hi - lo) / 2to avoid overflow.
The base-case bug: StackOverflowError
if (lo == hi) return; // wrong for a half-open range
Exception in thread "main" java.lang.StackOverflowError
at Main.sort(Main.java:10)
at Main.sort(Main.java:11)
at Main.sort(Main.java:11)
...
For a part of one element, lo = 0, hi = 1: mid = 0, sort(0, 0) returns, but sort(0, 1) calls itself with the same range, forever, until the call stack runs out. Every recursive call must make the problem smaller; a part of size 1 cannot be split, so it must be the base case: if (hi - lo <= 1) return;.
Two lakh numbers
int n = 200000;
int[] a = new int[n];
Random r = new Random(1);
for (int i = 0; i < n; i++) a[i] = r.nextInt(1000000);
long t0 = System.nanoTime();
mergeSort(a);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(a[0] + " " + a[n - 1] + " " + ms + " ms");
Output: 1 999988 181 ms (bubble sort on the same input: Time Limit Exceeded).
Why merge sort is O(n log n)
- Levels: the part sizes go n, n/2, n/4, ..., 1, so there are about log₂ n levels (18 for n = 2 × 10⁵).
- Work per level: all the merges on one level together touch each of the n elements once: O(n).
- Total: O(n log n), about 3.6 × 10⁶ steps for n = 2 × 10⁵, against 2 × 10¹⁰ for n²/2. That is over 5,000× less work.
- It is O(n log n) in the best, average and worst case: no input is bad for merge sort.
- Space: O(n) for
tmp, plus O(log n) for the recursion stack. Merge sort is not in-place.
Counting inversions
Brute force: check every pair
static long countBrute(int[] a) {
long count = 0;
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++)
if (a[i] > a[j]) count++;
return count;
}
On {5, 1, 4, 2, 8}, {}, {3, 3, 1, 3}, {1, 2, 3, 4, 5}, {5, 4, 3, 2, 1} it printed:
4
0
2
0
10
On two lakh random numbers: Time Limit Exceeded in the compiler. Run locally without a limit, it printed 10017630246 29537 ms: about 30 seconds for 2 × 10¹⁰ pair checks. O(n²).
The key insight: count while you merge
Every inversion is either inside the left half, inside the right half, or a cross pair (one element in each half). The recursion counts the first two. For the cross pairs, look at the merge of two sorted halves:
- When we take
a[j]from the right, it jumps ahead of every element still waiting in the left half,a[i..mid-1]. All of them are bigger thana[j](the left half is sorted anda[i] > a[j]), and all came before it in the original array. So that ismid - iinversions in one step. - Taking from the left jumps over nothing.
Last merge of our example: left [1, 4, 5], right [2, 8]. Taking 2 jumps over 4 and 5: +2 (the pairs (4,2) and (5,2)). The left half [5, 1, 4] contributed 2 more when it was sorted ((5,1) and (5,4)). Total 4.
The optimal solution in Java
static long count(int[] a) {
return sort(a, new int[a.length], 0, a.length);
}
static long sort(int[] a, int[] tmp, int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) / 2;
long count = sort(a, tmp, lo, mid) + sort(a, tmp, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi)
if (a[i] <= a[j]) tmp[k++] = a[i++];
else {
count += mid - i;
tmp[k++] = a[j++];
}
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
for (k = lo; k < hi; k++) a[k] = tmp[k];
return count;
}
Same five tests: 4, 0, 2, 0, 10. On the two lakh random numbers: 10017630246 146 ms: the same answer the brute force needed 30 seconds for.
The overflow bug
With int instead of long, on 2 × 10⁵ numbers in reverse order:
int n = 200000;
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = n - i;
System.out.println(count(a));
int version: -1474936480 (no error, no warning, a wrong answer). The true answer is n(n - 1)/2 = 19,999,900,000, far above Integer.MAX_VALUE = 2,147,483,647, so the int wrapped around (integer overflow). With long: 19999900000.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// merge sort + inversion count in one pass, on [lo, hi)
long long sortCount(vector<int>& a, vector<int>& tmp, int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) / 2;
long long count = sortCount(a, tmp, lo, mid) + sortCount(a, tmp, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi)
if (a[i] <= a[j]) tmp[k++] = a[i++];
else { count += mid - i; tmp[k++] = a[j++]; }
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
for (k = lo; k < hi; k++) a[k] = tmp[k];
return count;
}
long long countInversions(vector<int> a) { // takes a copy: the caller's array is unchanged
vector<int> tmp(a.size());
return sortCount(a, tmp, 0, a.size());
}
void mergeSort(vector<int>& a) {
vector<int> tmp(a.size());
sortCount(a, tmp, 0, a.size()); // sorts a; the count is ignored
}
int main() {
vector<int> a = {5, 1, 4, 2, 8};
cout << countInversions(a) << "\n";
mergeSort(a);
for (int x : a) cout << x << " ";
cout << "\n";
cout << countInversions({}) << " " << countInversions({3, 3, 1, 3}) << " "
<< countInversions({5, 4, 3, 2, 1}) << "\n";
int n = 200000;
vector<int> r(n);
for (int i = 0; i < n; i++) r[i] = n - i;
cout << countInversions(r) << "\n";
}
Output:
4
1 2 4 5 8
0 2 10
19999900000
The same solution in Python
import sys
def sort_count(a, tmp, lo, hi):
"""Sorts a[lo:hi] in place and returns its number of inversions."""
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
count = sort_count(a, tmp, lo, mid) + sort_count(a, tmp, mid, hi)
i, j, k = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]:
tmp[k] = a[i]; i += 1
else:
count += mid - i
tmp[k] = a[j]; j += 1
k += 1
while i < mid:
tmp[k] = a[i]; i += 1; k += 1
while j < hi:
tmp[k] = a[j]; j += 1; k += 1
a[lo:hi] = tmp[lo:hi]
return count
def count_inversions(a):
a = list(a) # work on a copy
return sort_count(a, [0] * len(a), 0, len(a))
def merge_sort(a):
sort_count(a, [0] * len(a), 0, len(a))
a = [5, 1, 4, 2, 8]
print(count_inversions(a))
merge_sort(a)
print(a)
print(count_inversions([]), count_inversions([3, 3, 1, 3]), count_inversions([5, 4, 3, 2, 1]))
n = 200000
print(count_inversions(range(n, 0, -1)))
Output:
4
[1, 2, 4, 5, 8]
0 2 10
19999900000
Python's integers never overflow, but recursion depth matters for other recursive code: here the depth is only about log₂ n ≈ 18.
Brute force vs optimal
| Approach | Time | Extra space | n = 2 × 10⁵ |
|---|---|---|---|
| Check every pair (inversions) | O(n²) | O(1) | 2 × 10¹⁰ steps: TLE (≈ 30 s) |
| Bubble / selection / insertion sort | O(n²) | O(1) | TLE |
| Merge sort | O(n log n) every case | O(n) + O(log n) stack | 181 ms |
| Count inversions while merging | O(n log n) | O(n) + O(log n) stack | 146 ms |
Merge sort is stable, not in-place, and not adaptive (sorted input still costs n log n). Java's Arrays.sort on objects uses TimSort, a merge sort variant that is adaptive.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
if (lo == hi) return; with [lo, hi) |
Exception in thread "main" java.lang.StackOverflowError |
a part of size 1 calls itself forever | if (hi - lo <= 1) return; |
int count for n up to 2 × 10⁵ |
-1474936480 on reversed input, no error |
the answer passes 2³¹ - 1 | long count (and long return types) |
a[i] < a[j] in the counting merge |
[3, 3, 1, 3] gives 5, not 2 |
ties take from the right, counting equal pairs | a[i] <= a[j] |
a[i] < a[j] in plain merge sort |
still sorted, but unstable | equal values swap order | <= |
| Forgetting the two leftover loops | elements silently lost / stale values | one pile empties first | copy the rest of both piles |
Forgetting to copy tmp back into a |
output not sorted | the merge result stays in tmp |
for (k = lo; k < hi; k++) a[k] = tmp[k]; |
count += mid - i + 1 with half-open ranges |
counts too many | that formula is for an inclusive mid |
mid - i when the left part is [lo, mid) |
Mini project: the movie-taste matcher
Read two friends' rankings of the same n movies (each a permutation of movie ids). Map the first friend's order to positions 0..n-1, build the array of the second friend's positions, and count inversions with merge sort. Print a similarity score 1 - inversions / (n(n - 1)/2) as a percentage. Test it with identical rankings (100%), reversed rankings (0%), and n = 2 × 10⁵ random rankings (it must run in well under a second).
Practice
- Count the inversions in
[8, 4, 2, 1]by hand, then run it.
Solution
It is reversed, so every pair is an inversion: 4 × 3 / 2 = 6. The program printed 6.
- Sort in descending order with merge sort.
Solution
Flip the merge comparison to a[i] >= a[j] (still = for stability). For [5, 1, 4, 2, 8] it printed [8, 5, 4, 2, 1].
- Merge two sorted arrays into a new array.
Solution
static int[] mergeArrays(int[] x, int[] y) {
int[] out = new int[x.length + y.length];
int i = 0, j = 0, k = 0;
while (i < x.length && j < y.length)
out[k++] = (x[i] <= y[j]) ? x[i++] : y[j++];
while (i < x.length) out[k++] = x[i++];
while (j < y.length) out[k++] = y[j++];
return out;
}
mergeArrays({1, 4, 5}, {2, 8}) printed [1, 2, 4, 5, 8]. O(n + m) time.
- Reverse pairs (hard): count pairs
i < jwitha[i] > 2 × a[j].
Solution
Same divide and conquer, but count before merging: both halves are sorted, so for each i in the left half move a pointer j forward in the right half while a[i] > 2 × a[j]; j never moves back, so the count is O(n) per level. Use long for 2 × a[j].
static long reversePairs(int[] a, int[] tmp, int lo, int hi) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) / 2;
long count = reversePairs(a, tmp, lo, mid) + reversePairs(a, tmp, mid, hi);
int j = mid;
for (int i = lo; i < mid; i++) { // both halves sorted: j only moves forward
while (j < hi && (long) a[i] > 2L * a[j]) j++;
count += j - mid;
}
int i = lo, k = lo; j = mid; // normal merge
while (i < mid && j < hi)
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
for (k = lo; k < hi; k++) a[k] = tmp[k];
return count;
}
[1, 3, 2, 3, 1] printed 2; [2, 4, 3, 5, 1] printed 3. O(n log n).
Quick quiz
What does System.out.println(count(new int[]{2, 4, 1, 3, 5})); print?
- 2
- 3
- 4
- 5
Answer
3: the pairs (2,1), (4,1) and (4,3). In the last merge, [2, 4] with [1, 3, 5]: taking 1 adds 2 (it jumps over 2 and 4), taking 3 adds 1 (it jumps over 4). The program printed 3.
Interview questions
- What is the time complexity of merge sort, and why? O(n log n) in every case: log n levels of splitting, O(n) merge work per level.
- What is its space complexity? O(n) for the temporary array plus O(log n) recursion stack. It is not in-place (in-place merging exists but is complicated and slow).
- Is merge sort stable? Yes, if the merge takes from the left on ties (
<=). - Merge sort or quick sort? Merge sort: guaranteed O(n log n), stable, great for linked lists and external sorting (data on disk). Quick sort: in-place and usually faster in memory, but O(n²) worst case (next episode).
- How do you count inversions in O(n log n)? Merge sort; whenever the merge takes from the right half, add
mid - i. - What does the inversion count tell you? How far the array is from sorted; it equals the number of bubble sort swaps and insertion sort shifts.
- Why sort a linked list with merge sort? Merging lists needs no extra array and no random access; splitting uses slow/fast pointers.
- What is the maximum inversion count, and which type holds it? n(n - 1)/2; for n = 2 × 10⁵ that is about 2 × 10¹⁰, so
long.
Glossary
| Term | Meaning |
|---|---|
| Divide and conquer | Split a problem into smaller parts, solve them (often recursively), then combine the answers |
| Recursion / recursive | A function that calls itself on a smaller input |
| Base case | The input small enough to answer directly, where the recursion stops (here: size 0 or 1) |
| Call stack | The memory where each active function call is remembered; it is limited |
StackOverflowError |
Java's error when the call stack runs out, usually from recursion that never stops |
| Merge | Combining two sorted sequences into one sorted sequence by repeatedly taking the smaller front element |
| Merge sort | Sort each half recursively, then merge them |
Half-open range [lo, hi) |
lo included, hi excluded; it has hi - lo elements |
mid |
The split point (lo + hi) / 2; the left part is [lo, mid), the right [mid, hi) |
Temporary array (tmp) |
Extra memory the merge writes into before copying back |
| In-place | Uses O(1) extra memory; merge sort is not |
| Stable | Equal values keep their original relative order |
| Inversion | A pair i < j with a[i] > a[j] |
| Cross pair | An inversion with one element in each half |
| O(n log n) | n times log₂ n: 2 × 10⁵ numbers ≈ 3.6 × 10⁶ steps |
| log₂ n | How many times you can halve n before reaching 1 (about 18 for 2 × 10⁵) |
| Integer overflow | A value too big for its type wraps around (int tops out at 2,147,483,647) |
long |
Java's 64-bit integer, up to about 9.2 × 10¹⁸ |
| Kendall tau distance | The inversion count between two rankings, used to compare them |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- Divide and conquer: split the array, sort each half recursively, merge. The base case is a part of size ≤ 1 (
hi - lo <= 1); getting it wrong givesStackOverflowError. - The merge takes the smaller front element (
<=keeps it stable) and copies the leftovers: O(n). - Merge sort is O(n log n) in every case and stable, with O(n) extra space: two lakh numbers in milliseconds.
- Counting inversions is merge sort plus one line: when the merge takes from the right,
count += mid - i. O(n log n) instead of O(n²). - The count can reach n(n - 1)/2 ≈ 2 × 10¹⁰: use
long, or it overflows silently.
Next episode: Quick sort and quickselect: kth largest element.