-
Notifications
You must be signed in to change notification settings - Fork 77
/
ConutingInversions.py
55 lines (40 loc) · 1.26 KB
/
ConutingInversions.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/bin/python3
import os
def merge(arr, left_half, right_half):
i, j, k = 0, 0, 0
inversions = 0
left_len, right_len = len(left_half), len(right_half)
while i < left_len and j < right_len:
if left_half[i] <= right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
inversions += left_len - i
k += 1
while i < left_len:
arr[k] = left_half[i]
i, k = i+1, k+1
while j < right_len:
arr[k] = right_half[j]
j, k = j+1, k+1
return inversions
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
left_half, right_half = arr[:mid], arr[mid:]
inversions = merge_sort(left_half) + merge_sort(right_half) + merge(arr, left_half, right_half)
return inversions
return 0
def countInversions(arr):
return merge_sort(arr)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
for t_itr in range(t):
n = int(input())
arr = list(map(int, input().rstrip().split()))
result = countInversions(arr)
fptr.write(str(result) + '\n')
fptr.close()