Counting inversions

Why it matters

Counting inversions shows how to take a known algorithm and carry extra information through it. You already know merge sort. This lesson changes nothing about how the array gets sorted, but it counts something useful while the sorting happens. This "modify the merge" trick appears in many interview problems, and it is the reason divide and conquer is more than a sorting method.

By the end of this lesson you will define an inversion, count inversions with a brute-force loop, count them in O(n log n) during a merge, and explain the two C++ traps that break naive versions of this code: the overflow of the count and the order in which function calls run.

The problem: how far from sorted?

An inversion is a pair of positions i and j with i < j and a[i] > a[j]. In plain words, it is a pair of values that are out of order: the bigger value comes first. The number of inversions measures how far an array is from being sorted.

Take the array 2 4 1 3 5. Look for pairs in the wrong order.

• 2 and 1: 2 comes first and is bigger, so that is an inversion.
• 4 and 1: 4 comes first and is bigger, so that is an inversion.
• 4 and 3: 4 comes first and is bigger, so that is an inversion.
• The other pairs are in order. For example 2 and 3, 1 and 5, and 3 and 5 are all in order.

So the array has 3 inversions. A sorted array has 0, because every pair is in order. A reversed array of n distinct values has the most, which is every pair: n * (n - 1) / 2. For five values that is 10.

Inversions are useful because they count "how many swaps of neighbours it would take to sort". Each swap of two neighbours that are out of order removes exactly one inversion. So the number of inversions is the minimum number of neighbour swaps needed to sort the array. You will see this in the exercises.

The brute force method

The simplest method checks every pair. Use two nested loops, and count each pair where the first value is bigger than the second.

Type this in the Input box, and press Run:

5
2 4 1 3 5

The output is 3. The method is correct, and it is easy to trust. The cost is the problem. The outer loop runs n times, and for each outer step the inner loop runs about n times, so the work is O(n squared). For 10 values that is about 45 comparisons, which is nothing. For 100000 values it is about 5 billion comparisons, which takes seconds to minutes. That is too slow for most real data, so the interview answer is to find a faster method.

The divide and conquer idea

Split the array into a left half and a right half. Every inversion falls into exactly one of three kinds.

1. Both values are in the left half.
2. Both values are in the right half.
3. One value is in the left half and the other is in the right half.

The first kind is found by counting inversions in the left half, which is the same problem on a smaller array. The second kind is found the same way on the right half. So the recursion can count kinds 1 and 2 for us. The question is how to count kind 3 quickly.

This is where merge sort helps. Recall that the recursion also sorts each half before merging. When the merge happens, both halves are sorted. Sorted halves have a special property that makes crossing inversions easy to count.

Here is the key step. Suppose the merge is at the point where the left front value is a[i], and the right front value is a[j], and the right value is smaller. In a sorted left half, every value from a[i] to the end of the left half is bigger than or equal to a[i], so each of those values is bigger than a[j]. Every one of them forms an inversion with a[j], because they all come before it. The number of such values is the number of left values from position i to the middle, which is mid - i + 1. One step of the merge adds that many inversions at once, instead of counting them one pair at a time.

The rule is short. When the merge takes a value from the right half, add mid - i + 1 to the count, where i is the current left index. When the merge takes a value from the left half, add nothing, because the left value is not bigger than the right value still waiting.

Trace the merge on a small example

The example below uses 2 4 1 3 5. Follow the merges by hand, then check the program. Notice that each merge uses sorted halves, so the rule above applies.

The top split is into 2 4 1 and 3 5. The left part 2 4 1 splits into 2 4 and 1. The first merge, of 2 4 with 1, takes 1 from the right first, because 2 is bigger than 1. At that moment the left index points at 2, and the left values from there to the middle are 2 and 4. So the step adds mid - i + 1 = 2. The sorted result is 1 2 4.

Next, the right part 3 5 has no inversions, because 3 is smaller than 5. Its merge adds nothing.

Last comes the top merge of 1 2 4 with 3 5. Take 1, then 2, both from the left, adding nothing. Next compare 4 with 3. The right value 3 is smaller, so it is taken, and the left index points at 4. The left values from 4 to the middle is just 4, so the step adds 1. Then 4 is taken, and finally 5. The top merge adds 1.

The total is 2 + 0 + 1 = 3, which matches the brute force count. The picture shows the top merge step by step, with the count added at each right value. The next program prints each merge and what it adds, so you can compare it with this trace.

The top merge of 1 2 4 with 3 5, showing that taking 3 adds one inversion because 4 is still waiting on the left

Press Run. You do not need input. The output is:

merge 0..1 adds 0
merge 0..2 adds 2
merge 3..4 adds 0
merge 0..4 adds 1
total 3

The first line is the merge of 2 and 4, which adds nothing, because they are in order. The second line is the merge of 2 4 with 1, which adds 2, matching the trace. The third line is 3 5, which adds nothing. The fourth line is the top merge, which adds 1. The lines appear in the order the merges finish, from the bottom of the tree upward, because the recursion finishes the small merges first.

Notice that the count is added only when a right value is taken. A left value taken first costs nothing, and a left value is never counted by itself. Every crossing pair is counted exactly once, at the moment its right value is taken. That is why the count is correct.

The full program

The next program is the complete counting method. It reads the array and prints the number of inversions. Compare it with the brute force program: both print 3 for the same input.

Type the same input as before, 5 and then 2 4 1 3 5, and press Run. The output is 3.

Look at the function countInv. It stores the results of the two recursive calls in variables before it calls mergeCount. This is not a style choice. It is required for correctness, and the next section explains why.

The evaluation order trap

Here is a tempting way to write the same function in one line.

return countInv(a, lo, mid) + countInv(a, mid + 1, hi) + mergeCount(a, lo, mid, hi);

It looks equivalent, and it may even give the right answer on your computer. But C++ does not promise the order in which the three function calls in one expression run. The compiler may run mergeCount first. If it does, mergeCount merges the two halves before they are sorted. The merge then takes values in the wrong order, and the count is wrong, sometimes silently and sometimes in a way that depends on the compiler or the optimisation level.

Two separate statements avoid the problem. A statement finishes before the next one starts, so the two recursive calls always finish, and both halves are sorted, before mergeCount runs. The order is now guaranteed by the statement order, not left to the compiler.

This is a general rule. In an expression, do not depend on the order in which function calls run, especially when a call changes data that another call reads. When one call sorts the data and another call merges it, use separate statements.

Big counts need big numbers

The number of inversions can be as large as n * (n - 1) / 2. For a reversed array of 100000 values that is 4999950000, which is almost five billion. A normal int in C++ holds about 2.1 billion at most, so the count would overflow. That is why the program uses long long, a 64-bit integer, for the count and every value that adds it up.

The next program reverses an array of size n and counts its inversions. It also prints the count converted to an int, to show what overflow does.

Type 100000 in the Input box, and press Run. The output is:

inversions 4999950000
as int 704982704

The first line is the right answer, which is 100000 * 99999 / 2. The second line is the same number forced into an int. The value wraps around, because the number is bigger than the largest int, and the program prints a meaningless small number. The output of that second line is what the gcc compiler prints for this conversion. The point is not the exact number. The point is that a count can silently be wrong when the type is too small, so choose the type from the largest value the answer can reach.

The mistake is common in interviews. If you see a count of pairs for a large input, check the type first.

Ties: why the comparison is <=

Equal values are not inversions. The definition needs a[i] > a[j], which is strict. The merge must match that. When the two front values are equal, take the left one first. The condition a[i] <= a[j] does exactly that. Then the right value is counted only when it is strictly smaller than the left front.

Suppose you wrote a[i] < a[j] by mistake. For the array 2 2, the two front values are equal. The condition is false, so the code takes the right value and counts it. The count becomes 1, but the correct count is 0, because two equal values are not out of order. The mistake is small, and the wrong answer is easy to miss in a quick test with distinct values.

Complexity

The method does the same sorting work as merge sort, and it adds only a few additions per merge. So the time is O(n log n), and the extra space is O(n) for the temporary vector in the merge. The brute force method uses O(1) extra space but O(n squared) time. The trade-off is classic: the faster method uses more memory and more careful code.

The Fenwick tree method, which you will see in the exercises, is another O(n log n) approach. It works in a different way, and it is worth knowing both.

Common mistakes

Using int for the count. As the reversed array example showed, the count can overflow. Use long long for the count and for every variable that adds up counts.

Writing inv += 1 instead of inv += mid - i + 1. This counts only one pair per merge step, not every left value that the right value passes. The count comes out much too small.

Using < instead of <= in the merge. Equal values are then counted as inversions, which is wrong. Use <=, which takes the left value first on a tie.

Counting before the halves are sorted. The rule mid - i + 1 depends on the left half being sorted. If the count runs before the recursion, the left values after i are not necessarily bigger than the right value, and the count is wrong. Do the recursion first, then count during the merge.

Calling the functions in one expression. As the evaluation-order section explained, this can merge unsorted halves. Put the calls in separate statements.

Forgetting the empty array. countInv(a, 0, n - 1) with n = 0 gives countInv(a, 0, -1). The base case lo >= hi returns 0 for that, so it is safe, but the program may still need a special case for reading the input. The program above checks it.

Debugging an inversion count

When the count is wrong, compare it with the brute force program on a small input. Find the smallest input where the two disagree, and then run the trace program on that input. The trace prints each merge and what it adds, so you can check the add value at each merge against the rule mid - i + 1.

If the trace shows a merge that adds too little, look for inv += 1 or a missing right-side count. If it adds too much, look for < instead of <=, which counts ties. If the total is right on small inputs but wrong on large ones, look at the type of the count.

Interview questions

Interviewers ask for inversions in several forms. They may ask for the brute force answer first, then for the O(n log n) method. They may ask why the method works, or what changes if the input contains duplicates. They may also ask for the minimum number of adjacent swaps to sort an array, and expect the answer to be the inversion count, with a reason.

A strong answer names the three kinds of pairs, explains why the merge counts crossing pairs, states the complexity, and mentions the overflow risk.

A bigger worked example

Take the array 5 3 2 4 1. Its inversions are the pairs (5, 3), (5, 2), (5, 4), (5, 1), (3, 2), (3, 1), (2, 1) and (4, 1). That is 8. Now run the divide and conquer count step by step. The trace program prints the same four merges, in the same order.

The total is the sum of the adds column: 1 + 2 + 1 + 4 = 8. The fourth merge alone adds 4. A bigger merge can hold many inversions, and each one is counted once, at the moment its right value is taken.

Notice how the left half of each merge is sorted before the merge starts. Merge 2 works on 3 5, which the first merge had just produced. Merge 4 works on 2 3 5 and 1 4, which the earlier merges had just sorted. The rule mid - i + 1 depends on that order, and the recursion provides it.

Why the count is complete

Every inversion is a pair of a left value and a right value, where the left value is bigger. Why is each such pair counted exactly once, and why is no pair missed?

The left half is sorted, so the values bigger than a particular right value y form the end of the left half. When the merge takes y, it has only taken left values that were smaller than or equal to y. So every left value bigger than y is still waiting, and those values are exactly the ones from the current left index to the middle. The formula mid - i + 1 counts exactly those values. Each right value is taken only once, so each right value's inversions are counted only once. Together, these facts show that every crossing pair is counted exactly once.

Edge cases for the count

An empty array has no pairs, and the program prints 0. A single value also has no pairs, and the base case returns 0.

A sorted array has 0 inversions. Every merge takes all its left values first, so nothing is added.

A reversed array has the most inversions, n * (n - 1) / 2. Every merge takes all its right values first.

All values equal also gives 0. With the <= tie rule, equal values never count as inversions, because the left value is taken first.

Negative values work exactly the same way as positive ones, because the rule only compares values.

Interview questions on inversions

A strong answer has four parts. First, the brute force method and its O(n squared) cost. Second, the divide and conquer recurrence: the work is two recursive calls on half-sized inputs plus a linear merge, which gives O(n log n) by the same level argument as merge sort. Third, the type of the answer, which must be long long. Fourth, the alternatives: a Fenwick tree works when the values are a small range, and the insertion sort count is a simple check when n is small.

Interviewers may also ask whether the answer changes if equal pairs count as inversions. It does, because the tie rule decides which pairs count, so the merge must take the right value on a tie instead of the left one.

A real use: comparing two rankings

Inversions measure disagreement between two rankings. Suppose two judges rank the same five contestants. Relabel each contestant by its position in the first ranking. Then read the second ranking as a list of those labels. The number of inversions in that list is the number of pairs the two judges ordered differently.

This count is called the Kendall tau distance. A distance of 0 means the rankings agree. The largest possible distance, n * (n - 1) / 2, means one ranking is the exact reverse of the other. Because the count takes O(n log n) time, the same method compares long rankings quickly, such as search results or chart positions.

Why the total work is O(n log n)

Write the work as a formula. Let T(n) be the work needed for n values. The count makes two recursive calls on halves, which together cost 2 T(n / 2). The merge then does about n steps. So the formula is T(n) = 2 T(n / 2) + n.

Unroll it level by level, as merge sort did. At the top there is one merge of size n. Below it there are two merges of size n / 2, which together cost n again. The next level has four merges of size n / 4, which also cost n in total. Each level costs n, and there are about log n levels before the pieces have one value. So the total is n times log n, which is O(n log n). This argument is the same as the one for merge sort, because the counting method has exactly the same shape. The only extra work is one addition per merge step.

A check with insertion

Insertion sort gives a second way to count inversions. It is slow, but it is easy to check by hand on a small array, and it is useful for testing the fast method.

Take 3 1 2. Start with 3, which is sorted by itself. Insert 1. It is smaller than 3, so it moves to the left of 3. That is one move, and one inversion. The array is now 1 3. Insert 2. It is smaller than 3, so it moves left past 3, which is a second move. It is bigger than 1, so it stops there. The array is 1 2 3, and the total number of moves is 2.

Each move in insertion sort removes exactly one inversion, and the moves stop only when no bigger value sits before the inserted one. So the number of moves equals the number of inversions. The method costs O(n squared) in the worst case, so it is only for checking, not for large inputs.

Testing your inversion code

Use a checklist, and run it every time you change the count.

Compare the fast count with the brute-force count on many small random arrays. Include arrays with duplicates, negative values, and values that repeat in long runs. These are the inputs where tie-handling bugs show up.

Test the empty array, one value, and two values in both orders. Test a sorted array, which must give 0, and a reversed array, which must give n * (n - 1) / 2.

Test a large reversed array, and check that the count does not overflow. A count of 4999950000 for 100000 values proves that the type is wide enough.

Finally, time the program on 100000 values, and confirm that it finishes well within a second. A wrong count often passes the sorted and reversed cases and fails only on the duplicate case, so always keep duplicates in your test set.

Trace the count on sorted and reversed arrays

The two extremes make the rule easy to see. Take the sorted array 1 2 3 4 first. The top split is 1 2 and 3 4. The left pair merges with no count, because 1 is taken, then 2 is taken, and nothing from the right is ever taken first. The right pair also adds nothing. The top merge takes 1 and 2 from the left, then the left half runs out and 3 and 4 are copied from the right. Nothing is added at any step, because no right value is ever taken while a left value waits. The total is 0, which is correct.

Now take the reversed array 4 3 2 1. The left pair 4 3 merges with a count of 1, because 3 is taken from the right while 4 waits. The right pair 2 1 also adds 1. The top merge has sorted halves 3 4 and 1 2. It takes 1 from the right while both 3 and 4 wait, which adds 2. It takes 2 from the right while both 3 and 4 still wait, which adds 2 again. Then it copies the rest. The total is 1 + 1 + 2 + 2 = 6, which equals 4 * 3 / 2, the largest possible count for four values.

The two traces show the range of the answer. A sorted array needs no counting at all, and a reversed array makes every merge count everything on its left.

A debugging story

A student wrote the merge with inv += 1 instead of inv += mid - i + 1. The code passed a quick test on 3 1 2, which happens to give the right answer for a reason explained below. Then it failed on 2 4 1. The correct count is 2, from the pairs (2, 1) and (4, 1). The printed answer was 1.

The trace explains it. The top call splits 2 4 1 into 2 4 and 1. The left half is already sorted, and the cross merge meets 1 on the right while both 2 and 4 are waiting on the left. The correct add is mid - i + 1, which is 2 at that moment. The += 1 version adds only 1, so the total is 1. The bug appears only when more than one left value waits behind a right value. The array 3 1 2 has only one waiting value at each step, so the bug hides there. This is why small examples can pass when the code is wrong, and why a random test with several values is worth writing.

Why both halves must be sorted first

The rule mid - i + 1 depends on the left half being sorted. In a sorted left half, every value after position i is bigger than or equal to the value at i, so every one of them forms an inversion with the right value. If the left half were not sorted, a value after i might be smaller than the right value, and the count would include a pair that is in order. The recursion makes the halves sorted before the merge runs, and that is the reason the count is correct. Counting before the recursion would give wrong answers even if the rest of the code were perfect.

An interview answer in four steps

Say the definition first: an inversion is a pair in the wrong order. Then say the brute force cost, O(n squared), and why it is too slow for large inputs. Next explain the divide and conquer count: the recursion gives the pairs inside each half, and the merge gives the crossing pairs, with the formula mid - i + 1 at each right value. Finally state the complexity, O(n log n) time and O(n) extra memory, and name the type you use for the count, long long. A candidate who gives these four parts is answering the question fully.

Follow-up questions interviewers ask next

After you give the O(n log n) answer, expect follow-ups. Each one tests a different part of the understanding.

What if the values are huge, such as 64-bit numbers? The merge only compares values, so it still works. A Fenwick tree would need the values compressed first, which means replacing each value with its rank among the sorted distinct values. Ranking takes one sort, and then the Fenwick method runs on small integers.

What if the data arrives as a stream, one value at a time? Then you cannot split the array in advance. A Fenwick tree handles this case, because it updates the count as each value arrives. It needs the value range to be known in advance, which is why compression is used.

How would you count pairs with a[i] > a[j] + k for a fixed k? The merge changes in one way. Before taking values, count the left values that are bigger than the right value plus k, using a second pointer that moves as the right value grows. The sorted halves make that pointer move in one direction only, so the count stays linear in each merge. This is the same pattern as the pairs-over-double problem in the module assignment.

How do you find the exact inversion count and also the sorted array? The same merge does both at once, which is why the counting method is a cheap extension of merge sort. Store the count in a variable, as the programs in this lesson do, and return the sorted array through the vector.

Practice

Work on paper first. Then check your code.

1. Count the inversions in 3 1 2 by hand. List each pair, then give the total.

2. Explain why a reversed array of n distinct values has n * (n - 1) / 2 inversions.

3. Count the pairs that are in order (where a[i] < a[j], with i < j) for an array with distinct values, using the inversion count. Explain why the two counts add up to the total number of pairs.

4. Count inversions with insertion sort. Each time insertion moves a value one place to the left past a bigger value, count one inversion. Write the function and test it on 3 1 2, which should give 2.

long long countByInsertion(vector<int> a) {
    long long count = 0;
    for (size_t i = 1; i < a.size(); i++) {
        int x = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > x) {
            a[j] = a[j - 1];
            j--;
            count++;
        }
        a[j] = x;
    }
    return count;
}

5. Explain what happens to the count in mergeCount if the condition a[i] <= a[j] is replaced with a[i] < a[j], using the array 2 2 as the input to the merge.

6. For each value in an array of distinct numbers, count how many values before it are bigger. Print one count per value. Write a brute force solution first, then say how divide and conquer could reach the same answer.

vector<int> biggerBefore(const vector<int>& a) {
    vector<int> out(a.size(), 0);
    for (size_t i = 0; i < a.size(); i++)
        for (size_t j = 0; j < i; j++)
            if (a[j] > a[i]) out[i]++;
    return out;
}

7. Count inversions with a Fenwick tree (also called a binary indexed tree). The values are a permutation of 1 to n. Walk through the loop for 3 1 2 and explain what the tree stores.

long long countWithBIT(const vector<int>& a, int n) {
    vector<int> bit(n + 1, 0);
    long long inv = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        int le = 0;
        for (int x = a[i]; x > 0; x -= x & -x) le += bit[x];
        inv += i - le;
        for (int x = a[i]; x <= n; x += x & -x) bit[x]++;
    }
    return inv;
}

8. Explain why the number of inversions equals the minimum number of swaps of neighbouring values needed to sort an array with distinct values. Then find the minimum number of neighbour swaps for 3 1 2.

What you now know

• An inversion is a pair of positions with the bigger value first.
• The brute force method counts every pair in O(n squared) time.
• A divide and conquer count splits the array, counts inversions inside each half, and counts the crossing pairs during the merge.
• During the merge, a right value taken while mid - i + 1 left values remain adds that many inversions at once.
• Use long long for the count, because it can be far bigger than an int.
• Call the recursive functions in separate statements, so the halves are sorted before the merge runs.
• Use <= in the merge, so equal values are not counted.
• The inversion count equals the minimum number of neighbour swaps needed to sort the array.