1 files changed, 38 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py b/AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py
new file mode 100644
index 0000000..cea3869
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py
@@ -0,0 +1,38 @@
+# Uses python3
+import sys
+
+def mergeInversionCount(B, C, D):
+    count = 0
+    while len(B) != 0 and len(C) != 0:
+        b = B[0]
+        c = C[0]
+        if b <= c:
+            D.append(b)
+            del B[0]
+        else:
+            count = count + len(B)
+            D.append(c)
+            del C[0]
+    D.extend(B)
+    D.extend(C)
+    return count
+
+
+def getInversionCount(A, D):
+    numOfInversions = 0
+    if len(A) == 1:
+        D.append(A[0])
+        return 0
+    m = int(len(A) / 2) 
+    D1 = []
+    numOfInversions = numOfInversions + getInversionCount(A[0:m], D1)
+    D2 = []
+    numOfInversions = numOfInversions + getInversionCount(A[m:len(A)], D2)
+    mergeCount = mergeInversionCount(D1, D2, D)
+    return numOfInversions + mergeCount
+
+if __name__ == '__main__':
+    input = sys.stdin.read()
+    n, *a = list(map(int, input.split()))
+    b = n * [0]
+    print(getInversionCount(a, b))
+\ No newline at end of file