Algorithms : complete 01-algorithmic_toolbox 03-divide_and_conquer

1 files changed, 34 insertions, 8 deletions

diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
index efc7a82..8400a2d 100644
--- a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
@@ -2,15 +2,41 @@
 #include <vector>
 
 using std::vector;
+using std::swap;
 
-long long get_number_of_inversions(vector<int> &a, vector<int> &b, size_t left, size_t right) {
-  long long number_of_inversions = 0;
-  if (right <= left + 1) return number_of_inversions;
-  size_t ave = left + (right - left) / 2;
-  number_of_inversions += get_number_of_inversions(a, b, left, ave);
-  number_of_inversions += get_number_of_inversions(a, b, ave, right);
-  //write your code here
-  return number_of_inversions;
+long long get_number_of_inversions(vector<int> &a, vector<int> &b, size_t left, size_t right)
+{
+    long long number_of_inversions = 0;
+    if (right <= left + 1) return number_of_inversions;
+    size_t ave = left + (right - left) / 2;
+    number_of_inversions += get_number_of_inversions(a, b, left, ave);
+    number_of_inversions += get_number_of_inversions(a, b, ave, right);
+
+    size_t i = left, j = ave, k = left;
+
+    while ((i != ave) && (j != right)) {
+        if (a[i] <= a[j]) {
+            b[k] = a[i];
+            i++;
+
+        } else {
+            b[k] = a[j];
+            j++;
+            number_of_inversions += (ave - i);
+        }
+        k++;
+    }
+
+    for( ; i != ave; i++, k++)
+        b[k] = a[i];
+
+    for( ; j != right; j++, k++)
+        b[k] = a[j];
+
+    for(i = left, k = left; i < right; i++, k++)
+        a[i] = b[k];
+
+    return number_of_inversions;
 }
 
 int main() {