How out of order is it?
Count the pairs that are in the wrong order while merge sort is merging, at almost no extra cost. About 16 minutes.
Count while merging
Checking every pair takes n times n steps. But think about merging two sorted halves. Say the left half is waiting with a few values and the right half's front is smaller than the left's front. That right value must jump ahead of every value still waiting on the left, and each of those is an inversion.
So add the number of values still waiting in the left half, all at once. Inversions inside each half are counted when the halves themselves are sorted.
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] > nums[j]:
count += 1- inversions
- 2
Fronts 3 and 1. The 1 goes first, jumping ahead of both 3 and 5, so add 2.
Add up three counts
The total for a list is the inversions inside the left half, plus the inversions inside the right half, plus the crossing ones found while merging. Every inverted pair is exactly one of those: both in the left half, both in the right, or one in each.
So the sort function should return two things: the sorted list and its inversion count. The answer for the whole list adds the three numbers together. Use a big enough number type, because a long reversed list has billions of inversions.
During a merge, the left half still has 4 values waiting and the right front is smaller than the left front. How many inversions does that step add?
- A4, one for each waiting left value
- B1, one for the right value
- C0, since the halves are each sorted
Show the answer
4, one for each waiting left value. The right value is smaller than the front, and all values behind it are at least as big.
Count the inversions
nums is a list of whole numbers. An inversion is a pair of positions i < j where nums[i] > nums[j]. Return how many inversions the list has.
nums = [2, 4, 1, 3, 5] → 3
0 ≤ length ≤ 100,000 · −1,000,000,000 ≤ value ≤ 1,000,000,000