How far the list is from sorted

An inversion is a pair of positions i < j where nums[i] > nums[j]: two values that are in the wrong order relative to each other. Count them.

A sorted list has none. A list sorted backwards has every possible pair, which is n(n-1)/2.

Worked example#

For [2, 4, 1, 3, 5] the inversions are (2,1), (4,1) and (4,3), so the answer is 3.

Why this is not a counting problem#

Checking every pair is n². On a hundred thousand numbers that is five billion comparisons, and the answer itself can be about five billion, so it does not even fit in a 32-bit integer.

There is no clever counting trick. What there is, is a sorting algorithm that happens to be able to count them for free, and that is why this problem is worth doing: it is the one that forces you to have actually implemented merge sort rather than called a library.

The idea#

Merge sort splits the list in half, sorts each half, and merges. Every inversion is in exactly one of three places: both positions in the left half, both in the right, or one in each. The first two are counted by the recursive calls. The third is counted during the merge, and it is nearly free.

While merging, you take the smaller of the two fronts. When you take a value from the right half, every value still waiting in the left half is larger than it and sits before it. So all of those are inversions, and there are exactly as many as remain in the left half:

if left[i] <= right[j]:  take left[i]
else:                    take right[j]; count += (how many are left in the left half)

One line added to a merge you were writing anyway.

Why it has to be merge sort#

The counting depends on both halves being sorted when they meet, which is what lets a single comparison stand in for a whole block of pairs. A sort that does not have that moment, such as quicksort, has nowhere to hang the count.

This is the clearest example of a general idea: sometimes the way to count something is to reorganise the data and let the reorganising do the counting.

Watch the size#

The answer can reach about five billion, which overflows a 32-bit integer. Use a 64-bit type for the count.

Constraints#

• 1 <= n <= 100000
• -1000000000 <= nums[i] <= 1000000000