-
Notifications
You must be signed in to change notification settings - Fork 223
/
ctci-merge-sort.py
40 lines (31 loc) · 1003 Bytes
/
ctci-merge-sort.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
import sys
def countInversions(array):
cnt_inv = 0
if len(array) <= 1:
return array, 0
ar_left, inv_left = countInversions(array[:int(len(array)/2)])
ar_right, inv_right = countInversions(array[int(len(array)/2):])
ar_merged = []
i = j = 0
len_left = len(ar_left)
len_right = len(ar_right)
for k in range(len(array) - 1):
if i == len_left or j == len_right:
break
if ar_left[i] <= ar_right[j]:
ar_merged.append(ar_left[i])
i += 1
else:
ar_merged.append(ar_right[j])
j += 1
cnt_inv += len_left - i
ar_merged += ar_left[i:]
ar_merged += ar_right[j:]
return ar_merged, cnt_inv + inv_left + inv_right
if __name__ == "__main__":
t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))
arr_sorted, result = countInversions(arr)
print(result)