From 886e0deedbaf1a53bbd6c37fac4337b80d30cae8 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 28 Nov 2018 20:08:23 -0600
Subject: Inversion count done!

It was easy, since I did the hard work of working it out in Java first.---
 .../sources/inversion_count.py                     | 38 ++++++++++++++++++++++
 1 file changed, 38 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/inversion_count.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources')

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
-- 
cgit v1.2.3