code_ex/CountInversionsMergeSort at master · pradeep17j/code_ex · GitHub

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#!/bin/python

import math
import os
import random
import re
import sys


def mergeSort(arr):

    if (len(arr)-1) == 1:

        return arr

    cnt = arr.pop(0)
    t_sz = len(arr)
    l_arr = arr[0:int(t_sz/2)]
    r_arr = arr[int(t_sz/2):]

    l_arr.insert(0,cnt)
    r_arr.insert(0,cnt)

    l_ret = mergeSort(l_arr)
    r_ret = mergeSort(r_arr)

    cnt = l_ret.pop(0) + r_ret.pop(0)


    i=j=0
    invs=0
    sorted = list()
    mid = len(l_ret)
    largest  = max(len(l_ret), len(r_ret))

    while(i < len(l_ret) and j < len(r_ret)):
        if l_ret[i] <= r_ret[j]:
            sorted.append(l_ret[i])
            i = i + 1

        elif r_ret[j] < l_ret[i]:
            sorted.append(r_ret[j])

            invs = invs + (mid - i)
            j = j + 1


    if (len(l_ret[i:]) > 0):
        sorted = sorted + l_ret[i:]
    elif (len(r_ret[j:]) > 0):
        sorted = sorted + r_ret[j:]

    cnt = cnt + invs

    sorted.insert(0,cnt)

    return sorted

# Complete the countInversions function below.
def countInversions(arr):

    if len(arr) == 0:
        return 0
    arr.insert(0,0)
    ret_arr = mergeSort(arr)
    count = ret_arr.pop(0)
    return count


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(raw_input())

    for t_itr in xrange(t):
        n = int(raw_input())

        arr = map(int, raw_input().rstrip().split())

        result = countInversions(arr)

        fptr.write(str(result) + '\n')

    fptr.close()