19.06Beginner / Intermediate3 topics20 min1 interactive animation

Inversions and counts

An inversion is a pair of elements that are out of order. Counting inversions measures how unsorted an array is, and merge sort counts them for free while it sorts. The same idea solves reverse pairs and count-smaller-after-self.

Learning goals

Define an inversion and relate it to insertion sort and bubble sort
Count inversions in O(n log n) during merge sort
Adapt the counting step for reverse pairs
Compute, for each element, how many smaller elements follow it

Prerequisites

Merge sortDivide and conquerTwo pointers

How different are two rankings of the same movies? Count the pairs the two people ordered differently. That count is an inversion count, and a merge sort can compute it in O(n log n) rather than checking every pair.

19.06.1

Count inversions via merge sort

An inversion is a pair of indices i < j with arr[i] > arr[j]. A sorted array has 0 inversions, a reverse sorted array of n elements has n(n - 1)/2. The count also equals the number of swaps bubble sort makes and the number of shifts insertion sort makes.

While merging two sorted halves, whenever you take an element from the right half before the remaining left elements, it is smaller than all of them and was after all of them in the original order. So it forms an inversion with each of the mid - i + 1 remaining left elements. Add that count and keep merging. The animation shows this count growing in the inversions counter.

Check the example [2, 4, 1, 3, 5]: the inversions are (2,1), (4,1) and (4,3), so the answer is 3, which the second preset reproduces.

Java

1static long inversions;
2
3static void merge(int[] arr, int[] buf, int lo, int mid, int hi) {
4    System.arraycopy(arr, lo, buf, lo, hi - lo + 1);
5    int i = lo, j = mid + 1;
6    for (int k = lo; k <= hi; k++) {
7        if (i > mid)              arr[k] = buf[j++];
8        else if (j > hi)          arr[k] = buf[i++];
9        else if (buf[j] < buf[i]) { arr[k] = buf[j++]; inversions += mid - i + 1; }   // right jumps over (mid - i + 1) left elements
10        else                      arr[k] = buf[i++];
11    }
12}

Worst

O(n log n)

Space

O(n)

Count inversions with merge sort

Interactive · edit the input

int[] arr · length 8

01234567

Being comparedSorted runOutside this call

Setup

Divide the 8 elements until single elements remain, then merge sorted runs back together.

Step 1 / 94

Java

1public static void mergeSort(int[] arr, int lo, int hi) {
2    if (hi - lo < 1) return;
3    int mid = lo + (hi - lo) / 2;
4    mergeSort(arr, lo, mid);
5    mergeSort(arr, mid + 1, hi);
6    merge(arr, lo, mid, hi);
7}
8
9static void merge(int[] arr, int lo, int mid, int hi) {
10    int[] tmp = new int[hi - lo + 1];
11    int i = lo, j = mid + 1, k = 0;
12    while (i <= mid && j <= hi) {
13        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
14        else { tmp[k++] = arr[j++]; inversions += mid - i + 1; }
15    }
16    while (i <= mid) tmp[k++] = arr[i++];
17    while (j <= hi) tmp[k++] = arr[j++];
18    System.arraycopy(tmp, 0, arr, lo, tmp.length);
19}

Live state

0 comparisons0 inversions

No condition evaluated on this step

Execution trace (dry run table)Show 94 steps

Step	Line	State	What happens
1	L1	n=8	Divide the 8 elements until single elements remain, then merge sorted runs back together.
2	L1	lo=0 hi=7 size=8	Enter mergeSort(arr, 0, 7) on 8 elements.
3	L2	lo=0 hi=7	More than one element, so split in half.
4	L3	lo=0 mid=3 hi=7	mid = 3. Left half [0..3], right half [4..7].
5	L4	lo=0 hi=3 size=4	Enter mergeSort(arr, 0, 3) on 4 elements.
6	L2	lo=0 hi=3	More than one element, so split in half.
7	L3	lo=0 mid=1 hi=3	mid = 1. Left half [0..1], right half [2..3].
8	L4	lo=0 hi=1 size=2	Enter mergeSort(arr, 0, 1) on 2 elements.
9	L2	lo=0 hi=1	More than one element, so split in half.
10	L3	lo=0 mid=0 hi=1	mid = 0. Left half [0..0], right half [1..1].
11	L4	lo=0 hi=0 size=1	Enter mergeSort(arr, 0, 0) on 1 element.
12	L2	lo=0 hi=0	Base case: one element is already sorted.
13	L5	lo=1 hi=1 size=1	Enter mergeSort(arr, 1, 1) on 1 element.
14	L2	lo=1 hi=1	Base case: one element is already sorted.
15	L10	lo=0 mid=0 hi=1 i=0 j=1 k=0	Allocate tmp for 2 elements. Left run [0..0] and right run [1..1] are each already sorted.
16	L13	lo=0 mid=0 hi=1 i=0 j=1 k=0	The right head is strictly smaller, so take it.
17	L14	lo=0 mid=0 hi=1 i=0 j=2 k=1	tmp[0] = 27. It jumps ahead of the 1 remaining left element, and each of those is larger, so that adds 1 inversion.
18	L16	lo=0 mid=0 hi=1 i=1 j=2 k=2	The left run still has 1 element. They are already sorted and no larger run remains, so copy them all.
19	L18	lo=0 mid=0 hi=1 i=1 j=2 k=2	Copy tmp back into arr[0..1]. That range is now sorted.
20	L5	lo=2 hi=3 size=2	Enter mergeSort(arr, 2, 3) on 2 elements.
21	L2	lo=2 hi=3	More than one element, so split in half.
22	L3	lo=2 mid=2 hi=3	mid = 2. Left half [2..2], right half [3..3].
23	L4	lo=2 hi=2 size=1	Enter mergeSort(arr, 2, 2) on 1 element.
24	L2	lo=2 hi=2	Base case: one element is already sorted.
25	L5	lo=3 hi=3 size=1	Enter mergeSort(arr, 3, 3) on 1 element.
26	L2	lo=3 hi=3	Base case: one element is already sorted.
27	L10	lo=2 mid=2 hi=3 i=2 j=3 k=0	Allocate tmp for 2 elements. Left run [2..2] and right run [3..3] are each already sorted.
28	L13	lo=2 mid=2 hi=3 i=2 j=3 k=0	The right head is strictly smaller, so take it.
29	L14	lo=2 mid=2 hi=3 i=2 j=4 k=1	tmp[0] = 3. It jumps ahead of the 1 remaining left element, and each of those is larger, so that adds 1 inversion.
30	L16	lo=2 mid=2 hi=3 i=3 j=4 k=2	The left run still has 1 element. They are already sorted and no larger run remains, so copy them all.
31	L18	lo=2 mid=2 hi=3 i=3 j=4 k=2	Copy tmp back into arr[2..3]. That range is now sorted.
32	L10	lo=0 mid=1 hi=3 i=0 j=2 k=0	Allocate tmp for 4 elements. Left run [0..1] and right run [2..3] are each already sorted.
33	L13	lo=0 mid=1 hi=3 i=0 j=2 k=0	The right head is strictly smaller, so take it.
34	L14	lo=0 mid=1 hi=3 i=0 j=3 k=1	tmp[0] = 3. It jumps ahead of the 2 remaining left elements, and each of those is larger, so that adds 2 inversions.
35	L13	lo=0 mid=1 hi=3 i=0 j=3 k=1	The left head is not larger, so take it. Using <= (left wins ties) is what makes merge sort stable.
36	L13	lo=0 mid=1 hi=3 i=1 j=3 k=2	tmp[1] = 27.
37	L13	lo=0 mid=1 hi=3 i=1 j=3 k=2	The left head is not larger, so take it. Using <= (left wins ties) is what makes merge sort stable.
38	L13	lo=0 mid=1 hi=3 i=2 j=3 k=3	tmp[2] = 38.
39	L17	lo=0 mid=1 hi=3 i=2 j=4 k=4	The right run still has 1 element. They are already sorted and no larger run remains, so copy them all.
40	L18	lo=0 mid=1 hi=3 i=2 j=4 k=4	Copy tmp back into arr[0..3]. That range is now sorted.
41	L5	lo=4 hi=7 size=4	Enter mergeSort(arr, 4, 7) on 4 elements.
42	L2	lo=4 hi=7	More than one element, so split in half.
43	L3	lo=4 mid=5 hi=7	mid = 5. Left half [4..5], right half [6..7].
44	L4	lo=4 hi=5 size=2	Enter mergeSort(arr, 4, 5) on 2 elements.
45	L2	lo=4 hi=5	More than one element, so split in half.
46	L3	lo=4 mid=4 hi=5	mid = 4. Left half [4..4], right half [5..5].
47	L4	lo=4 hi=4 size=1	Enter mergeSort(arr, 4, 4) on 1 element.
48	L2	lo=4 hi=4	Base case: one element is already sorted.
49	L5	lo=5 hi=5 size=1	Enter mergeSort(arr, 5, 5) on 1 element.
50	L2	lo=5 hi=5	Base case: one element is already sorted.
51	L10	lo=4 mid=4 hi=5 i=4 j=5 k=0	Allocate tmp for 2 elements. Left run [4..4] and right run [5..5] are each already sorted.
52	L13	lo=4 mid=4 hi=5 i=4 j=5 k=0	The left head is not larger, so take it. Using <= (left wins ties) is what makes merge sort stable.
53	L13	lo=4 mid=4 hi=5 i=5 j=5 k=1	tmp[0] = 9.
54	L17	lo=4 mid=4 hi=5 i=5 j=6 k=2	The right run still has 1 element. They are already sorted and no larger run remains, so copy them all.
55	L18	lo=4 mid=4 hi=5 i=5 j=6 k=2	Copy tmp back into arr[4..5]. That range is now sorted.
56	L5	lo=6 hi=7 size=2	Enter mergeSort(arr, 6, 7) on 2 elements.
57	L2	lo=6 hi=7	More than one element, so split in half.
58	L3	lo=6 mid=6 hi=7	mid = 6. Left half [6..6], right half [7..7].
59	L4	lo=6 hi=6 size=1	Enter mergeSort(arr, 6, 6) on 1 element.
60	L2	lo=6 hi=6	Base case: one element is already sorted.
61	L5	lo=7 hi=7 size=1	Enter mergeSort(arr, 7, 7) on 1 element.
62	L2	lo=7 hi=7	Base case: one element is already sorted.
63	L10	lo=6 mid=6 hi=7 i=6 j=7 k=0	Allocate tmp for 2 elements. Left run [6..6] and right run [7..7] are each already sorted.
64	L13	lo=6 mid=6 hi=7 i=6 j=7 k=0	The left head is not larger, so take it. Using <= (left wins ties) is what makes merge sort stable.
65	L13	lo=6 mid=6 hi=7 i=7 j=7 k=1	tmp[0] = 10.
66	L17	lo=6 mid=6 hi=7 i=7 j=8 k=2	The right run still has 1 element. They are already sorted and no larger run remains, so copy them all.
67	L18	lo=6 mid=6 hi=7 i=7 j=8 k=2	Copy tmp back into arr[6..7]. That range is now sorted.
68	L10	lo=4 mid=5 hi=7 i=4 j=6 k=0	Allocate tmp for 4 elements. Left run [4..5] and right run [6..7] are each already sorted.
69	L13	lo=4 mid=5 hi=7 i=4 j=6 k=0	The left head is not larger, so take it. Using <= (left wins ties) is what makes merge sort stable.
70	L13	lo=4 mid=5 hi=7 i=5 j=6 k=1	tmp[0] = 9.
71	L13	lo=4 mid=5 hi=7 i=5 j=6 k=1	The right head is strictly smaller, so take it.
72	L14	lo=4 mid=5 hi=7 i=5 j=7 k=2	tmp[1] = 10. It jumps ahead of the 1 remaining left element, and each of those is larger, so that adds 1 inversion.
73	L13	lo=4 mid=5 hi=7 i=5 j=7 k=2	The right head is strictly smaller, so take it.
74	L14	lo=4 mid=5 hi=7 i=5 j=8 k=3	tmp[2] = 15. It jumps ahead of the 1 remaining left element, and each of those is larger, so that adds 1 inversion.
75	L16	lo=4 mid=5 hi=7 i=6 j=8 k=4	The left run still has 1 element. They are already sorted and no larger run remains, so copy them all.
76	L18	lo=4 mid=5 hi=7 i=6 j=8 k=4	Copy tmp back into arr[4..7]. That range is now sorted.
77	L10	lo=0 mid=3 hi=7 i=0 j=4 k=0	Allocate tmp for 8 elements. Left run [0..3] and right run [4..7] are each already sorted.
78	L13	lo=0 mid=3 hi=7 i=0 j=4 k=0	The left head is not larger, so take it. Using <= (left wins ties) is what makes merge sort stable.
79	L13	lo=0 mid=3 hi=7 i=1 j=4 k=1	tmp[0] = 3.
80	L13	lo=0 mid=3 hi=7 i=1 j=4 k=1	The right head is strictly smaller, so take it.
81	L14	lo=0 mid=3 hi=7 i=1 j=5 k=2	tmp[1] = 9. It jumps ahead of the 3 remaining left elements, and each of those is larger, so that adds 3 inversions.
82	L13	lo=0 mid=3 hi=7 i=1 j=5 k=2	The right head is strictly smaller, so take it.
83	L14	lo=0 mid=3 hi=7 i=1 j=6 k=3	tmp[2] = 10. It jumps ahead of the 3 remaining left elements, and each of those is larger, so that adds 3 inversions.
84	L13	lo=0 mid=3 hi=7 i=1 j=6 k=3	The right head is strictly smaller, so take it.
85	L14	lo=0 mid=3 hi=7 i=1 j=7 k=4	tmp[3] = 15. It jumps ahead of the 3 remaining left elements, and each of those is larger, so that adds 3 inversions.
86	L13	lo=0 mid=3 hi=7 i=1 j=7 k=4	The left head is not larger, so take it. Using <= (left wins ties) is what makes merge sort stable.
87	L13	lo=0 mid=3 hi=7 i=2 j=7 k=5	tmp[4] = 27.
88	L13	lo=0 mid=3 hi=7 i=2 j=7 k=5	The left head is not larger, so take it. Using <= (left wins ties) is what makes merge sort stable.
89	L13	lo=0 mid=3 hi=7 i=3 j=7 k=6	tmp[5] = 38.
90	L13	lo=0 mid=3 hi=7 i=3 j=7 k=6	The left head is not larger, so take it. Using <= (left wins ties) is what makes merge sort stable.
91	L13	lo=0 mid=3 hi=7 i=4 j=7 k=7	tmp[6] = 43.
92	L17	lo=0 mid=3 hi=7 i=4 j=8 k=8	The right run still has 1 element. They are already sorted and no larger run remains, so copy them all.
93	L18	lo=0 mid=3 hi=7 i=4 j=8 k=8	Copy tmp back into arr[0..7]. That range is now sorted.
94	L6		Sorted. Total inversions counted: 15 (pairs i < j with arr[i] > arr[j]).

19.06.2

Reverse pairs

Reverse pairs counts pairs i < j with nums[i] > 2 * nums[j]. The condition is not the same as the merge condition, so count in a separate loop before merging, while both halves are sorted.

For each i in the left half in increasing order, advance j through the right half while nums[i] > 2 * nums[j]. Because nums[i] only grows, j never moves backwards, so the loop is linear. Then run the normal merge. The multiplication must be done in long, since 2 * nums[j] can overflow int.

Java

1static int reversePairs(int[] nums) {
2    return sort(nums, new int[nums.length], 0, nums.length - 1);
3}
4
5private static int sort(int[] a, int[] buf, int lo, int hi) {
6    if (lo >= hi) return 0;
7    int mid = lo + (hi - lo) / 2;
8    int count = sort(a, buf, lo, mid) + sort(a, buf, mid + 1, hi);
9    int j = mid + 1;
10    for (int i = lo; i <= mid; i++) {                       // both halves are sorted here
11        while (j <= hi && (long) a[i] > 2L * a[j]) j++;
12        count += j - (mid + 1);
13    }
14    merge(a, buf, lo, mid, hi);                             // ordinary merge afterwards
15    return count;
16}

Worst

O(n log n)

Space

O(n)

19.06.3

Count smaller elements after self

For each index i, count the elements to its right that are smaller than nums[i]. This is an inversion count per element. Sort indices instead of values, so each element keeps its identity as the merge moves it.

In each merge, track how many right-half elements have been placed so far. When a left element is placed, every right element already placed is smaller than it and was originally to its right, so add that number to the left element's answer. Take the left element on ties, so only strictly smaller right elements are counted.

nums	Smaller elements to the right
[5, 2, 6, 1]	[2, 1, 1, 0]
[-1, -1]	[0, 0]
[3, 2, 1]	[2, 1, 0]

Java

1static List<Integer> countSmaller(int[] nums) {
2    int n = nums.length;
3    int[] idx = new int[n], tmp = new int[n], ans = new int[n];
4    for (int i = 0; i < n; i++) idx[i] = i;
5    sort(nums, idx, tmp, ans, 0, n - 1);
6    return Arrays.stream(ans).boxed().toList();
7}
8
9private static void sort(int[] nums, int[] idx, int[] tmp, int[] ans, int lo, int hi) {
10    if (lo >= hi) return;
11    int mid = lo + (hi - lo) / 2;
12    sort(nums, idx, tmp, ans, lo, mid);
13    sort(nums, idx, tmp, ans, mid + 1, hi);
14    int i = lo, j = mid + 1, k = lo, rightPlaced = 0;
15    while (i <= mid || j <= hi) {
16        if (j > hi || (i <= mid && nums[idx[i]] <= nums[idx[j]])) {
17            ans[idx[i]] += rightPlaced;                     // smaller elements from the right half
18            tmp[k++] = idx[i++];
19        } else {
20            rightPlaced++;
21            tmp[k++] = idx[j++];
22        }
23    }
24    System.arraycopy(tmp, lo, idx, lo, hi - lo + 1);
25}

Worst

O(n log n)

Space

O(n)

Practice ladder

Now try it yourself

Easy

Count inversions in an array of at most 10 elements by brute force
Is an array sorted, and how far is it from sorted?

Medium

Count inversions in O(n log n)
Reverse pairs
Count of smaller numbers after self

Advanced

Count range sums with merge sort
Global and local inversions
Count inversions with a Fenwick tree and compare with the merge version

Key takeaways

An inversion is a pair i < j with arr[i] > arr[j]; the count equals bubble sort's swaps and insertion sort's shifts.
Merge sort counts them in O(n log n): when a right element is taken first, it inverts with all remaining left elements.
Reverse pairs counts in a pass before merging; count-smaller sorts indices and uses the number of right elements placed so far.