Counting inversions during merge sort
Measure how far a sequence is out of order by counting inversions. A worked merge shows how one comparison can count a whole run and why equal values need care.
Two devices upload six samples with shared sequence numbers [4, 1, 4, 2, 0, 3] in arrival order. An engineer counting adjacent drops sees three: 4 to 1, 4 to 2, and 2 to 0. Another engineer asks how many pairs of samples arrived in the wrong relative order. Her answer is nine. Sorting the log gives both engineers the same tidy report and erases the evidence needed to settle the question.
An inversion is a pair of positions where the earlier value is strictly greater than the later one. The first 4 alone forms four inversions, one with each of 1, 2, 0 and 3. The second 4 counts separately because it came from a different position. The two 4s form no inversion with each other. That definition gives you a short piece of code you can trust on small inputs.
static long CountPairs(int[] input)
{
long count = 0;
for (int first = 0; first < input.Length; first++)
for (int second = first + 1; second < input.Length; second++)
if (input[first] > input[second]) count++;
return count;
}On a log with 200,000 samples those loops compare 19,999,900,000 pairs, even when every sample is already in order. Listing every inversion could require an output of that size. Counting them only requires one number. The trick is finding a comparison that settles the question for a whole group of pairs at once.
Cut the original log into a left half and a right half. Every pair belongs to exactly one of three groups: both positions in the left half, both in the right, or one on each side. The first two are smaller versions of the original question. Once you have counted a half's internal inversions, you are free to sort that half. No information needed for the third group has been lost. Every sample on the left still arrived before every sample on the right.
In the example the left half [4, 1, 4] has one internal inversion, and the right half [2, 0, 3] has one. Sort the halves to get [1, 4, 4] and [0, 2, 3]. Consider the right-hand 0. The smallest remaining value on the left is 1. A single comparison proves that every value still on the left exceeds 0. You can add three to the count and emit the 0 into the merged output.
-
Emit the right-hand 0
- 1
- 4
- 4
All three remaining left values exceed 0. Add three pairs.
-
Emit the left-hand 1
- 1
- 4
- 4
1 comes before the next right value, 2. Remove it from consideration.
-
Emit the right-hand 2
- 4
- 4
Both remaining left positions exceed 2. Add two pairs.
-
Emit the right-hand 3
- 4
- 4
Both also exceed 3. Add two more. Draining the remaining 4s adds nothing.
Each emitted right value accounts for all its cross inversions at once. Left values that have already been emitted were at most as large as the right value next in line at the time. Since the right half is sorted, they cannot exceed any later right value either. Add the seven cross pairs to the two internal pairs and you recover the nine inversions in the arrival log.
Try merging the left run [2, 4] with the right run [2, 3]. If an ordinary merge takes the right-hand 2 first on a tie, it still produces correctly sorted output. An inversion counter that adds the remaining left length on that branch would count two pairs immediately. Only one of the two left values actually exceeds 2. The other is an equal. A test that checks the final sort order misses the error completely.
Emit the left value on a tie. When the right value wins, every remaining left position is a strictly larger predecessor.
The merge below writes into a scratch array and copies the merged run back to a working copy of the input. Each recursive call owns a half-open range. Its middle index is both the end of the left range and the start of the right. If left points to the next left item, middle - left is exactly how many remain. Mixing an inclusive end with that formula is an easy way to lose one pair at every split.
static long CountInversions(int[] input)
{
int[] values = (int[])input.Clone();
var scratch = new int[input.Length];
return CountRange(0, values.Length);
long CountRange(int start, int end)
{
if (end - start < 2) return 0;
int middle = start + (end - start) / 2;
long count = CountRange(start, middle) + CountRange(middle, end);
if (values[middle - 1] <= values[middle]) return count;
int left = start;
int right = middle;
for (int write = start; write < end; write++)
{
if (right == end || (left < middle && values[left] <= values[right]))
{
scratch[write] = values[left++];
}
else
{
scratch[write] = values[right++];
count += middle - left;
}
}
Array.Copy(scratch, start, values, start, end - start);
return count;
}
}The helper promises two things on return. Its number is the inversion count within the original range, and its part of values is now sorted. The parent needs both promises. Sorting the caller's array in place could save one copy but changes the evidence that a caller might want to replay. Allocating a new scratch array in every call creates a different cost: many short-lived arrays even though two sibling calls never need the same scratch space at once.
The check just after the recursive calls compares the largest left value with the smallest right value. If the left one is already in order, the full range is sorted and there are zero cross inversions. The two halves may still have contained plenty of internal inversions. Returning count there, instead of zero, preserves the work both children just did. A four-value input like [2, 1, 4, 3] exercises that exact path at the root.
A merge processes at most one element per output slot. All the merges at one depth together process at most the length of the log, and repeatedly halving the ranges gives O(log n) depths. Worst-case time is O(n log n). The two working arrays use O(n) space, with O(log n) stack frames. The ordered-boundary check allows an already sorted input to pass in linear time. Princeton's mergesort material describes both the inversion-count application and the ordered-boundary optimization. Algorithms, 4th Edition, on mergesort
Begin with a descending array of 65,537 distinct values. Every pair is inverted, so the expected count is 2,147,516,416. That is just above the largest signed 32-bit integer. A method can return long and still fail this case if it accumulates into an int and widens the result on return. Widen before multiplying when calculating the expected value too. With an all-equal array of the same length the correct answer is zero.
For a small random log, compare against the double loop and make sure the original array still matches a saved copy. For a larger log, reverse the input and count again. Every unequal pair is inverted in exactly one of the two directions. An equal pair contributes in neither direction. The two counts must therefore add up to the number of unordered position pairs minus the number whose values are equal. That relation gives you a check at sizes where the double loop is too expensive. It is also a useful starting point for property-based testing.
Katabench's Count Inversions exercise keeps the input read-only and includes inputs large enough to distinguish the merge from pair enumeration. The performance guide explains the time budgets. If the merge itself is the unfamiliar part, start with Merge Sorted Arrays in the C# challenge catalog and add a counter only after you can explain both outcomes of the next comparison.
Practice what you just read
- Open in the editor: Count Inversions
Algorithm Hard Free, no account needed
Count Inversions
Count every out-of-order pair without examining every pair.
- Open in the editor: Merge Sorted Arrays
Algorithm Easy Free, no account needed
Merge Sorted Arrays
Merge two sorted arrays into one - without destroying what makes them special.
More like this: C# coding challenges →