Sort a list, and count how out of order it was.
What to build
Merge sort, extended to count inversions.
Requirements
- Read the numbers.
- Print them in sorted order, using your own merge sort.
- Print
inversions C, the number of position pairsi < jwith the value atigreater than the value atj.
Input
The first line has n. The second line has n whole numbers.
Output
Two lines.
Constraints
n is from 1 to 2000.
Example
Input:
5
2 4 1 3 5
Output:
1 2 3 4 5
inversions 3
Why it works
In the merge step, the left half is sorted, so when a right item goes first it must be smaller than every item left there. Adding that count at once avoids comparing every pair.
Examples
Example 1 · Input
5 2 4 1 3 5
Expected output
1 2 3 4 5 inversions 3
Example 2 · Input
3 1 2 3
Expected output
1 2 3 inversions 0
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Split the list in half, sort each half, and merge them.
Hint 2
When an item from the right half goes first, it jumps over all the items left in the left half.
Hint 3
Have the function return both the sorted list and the count.
Solution
Show one correct solution (try it yourself first)
def sort_count(nums):
if len(nums) <= 1:
return nums, 0
middle = len(nums) // 2
left, a = sort_count(nums[:middle])
right, b = sort_count(nums[middle:])
merged = []
count = a + b
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
count += len(left) - i
return merged + left[i:] + right[j:], count
n = int(input())
result, count = sort_count([int(x) for x in input().split()])
print(" ".join(str(x) for x in result))
print("inversions", count)