# Merge Sort: Counting Inversions

# Merge Sort: Counting Inversions

RachelAF + 16 comments Make sure that you use a long to track the swaps! If you use an int, you'll get the wrong answer due to integer overflow in the last third or so of the cases.

jonmcclung + 1 comment Wish this comment had been higher up. It would have saved me a good bit of time.

yashpalsinghdeo1 + 0 comments here is problem solution in

**python java c++**and**c**programming language. https://solution.programmingoneonone.com/2020/07/hackerrank-merge-sort-counting-inversions-solution.html

kmshihabuddin + 0 comments [deleted]cambec + 0 comments Thanks for pointing this out. I'm not sure how I feel about this additional trap after I was so soundly battered by the core problem. No mercy in CS...

djv + 38 comments In case you're struggling with Python timing out on the last 3 test cases. Just switch to PyPy as the language, you can use the same code but it runs faster. Assuming you've implemented the O(n Log n) algorithm then all the tests will pass.

VictorA + 0 comments Wow. Thank you. I was wondering what was going on...

this_aaron + 0 comments I was timing out on Python 3, same code passed on PyPy2

episodeyang + 4 comments tested on both pypy2 and 3, starts to timeout on some of the earlier test cases.

code is below:

def sort_pair(arr0, arr1): if len(arr0) > len(arr1): return arr1, arr0 else: return arr0, arr1 def merge(arr0, arr1): inversions = 0 result = [] while len(arr0) > 0 and len(arr1) > 0: if arr0[0] <= arr1[0]: result.append(arr0.pop(0)) else: # count the inversion right here: add the length of left array inversions += len(arr0) result.append(arr1.pop(0)) if len(arr0) == 0: result += arr1 elif len(arr1) == 0: result += arr0 return result, inversions def sort(arr): length = len(arr) mid = length//2 if length >= 2: sorted_0, counts_0 = sort(arr[:mid]) sorted_1, counts_1 = sort(arr[mid:]) result, counts = merge(sorted_0, sorted_1) return result, counts + counts_0 + counts_1 else: return arr, 0 def count_inversions(a): final_array, inversions = sort(a) # print(final_array) return inversions t = int(input().strip()) for a0 in range(t): n = int(input().strip()) arr = list(map(int, input().strip().split(' '))) print(count_inversions(arr))

danielgomezrico + 1 comment I was getting a timeout because of temporal array init inside of each merge(), put the init of it outside and pass it to avoid init on each iteration :) (I do it with java)

Lherbeur + 1 comment I tried this. initd the merge arrays outside the recursive calls and passed them in but it still times out on some test cases. Could you figure out why?

import java.io.

*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.Map.Entry; import java.util.concurrent.*; import java.util.regex.*;public class Solution {

`// Complete the countInversions function below.`

static long countInversions(int[] arr) {

`long inversionsCount = 0; int [] lowerArray = new int [arr.length]; int [] higherArray = new int [arr.length]; //frm mid+1 to high inversionsCount = countAndSort (arr, 0, arr.length - 1, lowerArray, higherArray); return inversionsCount; } static long countAndSort(int [] arr, int low, int high, int [] lowerArray, int [] higherArray) { long totalCount = 0; long count = 0; if (low < high) { int mid = low + (high-low) /2; long lowerCount = countAndSort (arr, low, mid, lowerArray, higherArray); long higherCount = countAndSort (arr, mid+1, high, lowerArray, higherArray); totalCount += lowerCount + higherCount + countAndSortMerge (arr, low, mid, high, lowerArray, higherArray); } return totalCount; } static long countAndSortMerge(int [] arr, int low, int mid, int high, int [] lowerArray, int [] higherArray) { long countInversions = 0; for (int i=0; i< (mid-low+1);i++) { lowerArray[i] = arr [low+i]; } for (int i=0; i< (high-mid);i++) { higherArray[i] = arr [mid+1+i]; } int lowIndex = 0; int highIndex = 0; int arrIndex = low; while (lowIndex < (mid-low+1) && highIndex < (high-mid)) { if (lowerArray[lowIndex] <= higherArray [highIndex]) { arr[arrIndex] = lowerArray[lowIndex]; ++lowIndex; } else { arr[arrIndex] = higherArray[highIndex]; ++highIndex; countInversions += (mid-low+1 - lowIndex); } ++arrIndex; } while (lowIndex < (mid-low+1)) { arr[arrIndex] = lowerArray[lowIndex]; ++lowIndex; ++arrIndex; } while (highIndex < (high-mid)) { arr[arrIndex] = higherArray[highIndex]; ++highIndex; ++arrIndex; } System.out.printf("CountandsortMerge inversions - %d", countInversions); return countInversions; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int t = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int tItr = 0; tItr < t; tItr++) { int n = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); int[] arr = new int[n]; String[] arrItems = scanner.nextLine().split(" "); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int i = 0; i < n; i++) { int arrItem = Integer.parseInt(arrItems[i]); arr[i] = arrItem; } long result = countInversions(arr); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); } bufferedWriter.close(); scanner.close(); }`

}

aaronkb9 + 3 comments @episodeyang: your algorithm is correct but it's slowed down by running array.pop(0). That's an O(n) operation in python. I modified your merge function to use two indices to keep track of where I was in each array and ran it in pypy3 and it passed. See code below:

def merge(arr0, arr1): inversions = 0 result = [] # two indices to keep track of where we are in the array i0 = 0 i1 = 0 # probably doesn't really save much time but neater than calling len() everywhere len0 = len(arr0) len1 = len(arr1) while len0 > i0 and len1 > i1: if arr0[i0] <= arr1[i1]: result.append(arr0[i0]) i0 += 1 else: # count the inversion right here: add the length of left array inversions += len0 - i0 result.append(arr1[i1]) i1 += 1 if len0 == i0: result += arr1[i1:] elif len1 == i1: result += arr0[i0:] return result, inversions

timnosov + 3 comments Actually len() also matters, especially inside the loop. I had

inversions += len(arr0[i0:])

instead of

inversions += len0 - i0

and it was timing out because when slicing, Python creates a copy, making it O(n) opperation.

Thank you for the code.

vonalogue + 0 comments I also used indices. Additionally, I used nested functions to avoid generating new arrays by keeping the original and the auxiliary one in scope (along with a "Context" class to make the counter variable accessible).

Instead of using built-in functions or slicing to build the new array, I just iterated through it and assigned each element a new value. I made this possible by initializing the new array as a pointer to the original and initializing the auxiliary one as a copy of the original; this way, we have a pre-determined size that allows for iteration.

P.S. This was written in Python 2 (without using PyPy). This times out on the last three cases.

#!/bin/python import sys def merge_sort(arr): class Context: count = 0 def merge(*indices): # indices = first, last, and pivot indices, respectively head, tail = indices[0], indices[1] pivot = indices[2] i = head j = pivot+1 k = 0 while (i <= pivot and j <= tail): if new[i] <= new[j]: aux[k] = new[i] i += 1 k += 1 else: aux[k] = new[j] j += 1 k += 1 Context.count += pivot - i+1 while (i <= pivot): aux[k] = new[i] i += 1 k += 1 while (j <= tail): aux[k] = new[j] j += 1 k += 1 for x in xrange(head, tail+1): new[x] = aux[x-head] # end merge def split(a, *indices): # indices = first and last indices, respectively head, tail = indices[0], indices[1] pivot = (head+tail) / 2 if head < tail: l_sub = a[head:pivot+1] r_sub = a[pivot+1:tail+1] split(l_sub, head, pivot) split(r_sub, pivot+1, tail) merge(head, tail, pivot) # end split new = arr aux = list(new) tail = len(new)-1 split(new, 0, tail) return Context.count # end merge_sort if __name__ == "__main__": loops = int(raw_input().strip()) for _ in xrange(loops): useless_var = int(raw_input().strip()) arr = map(int, raw_input().strip().split(' ')) result = merge_sort(arr) print result

ranos + 1 comment Guys please help,

Why is:

inversions = len0-i0

Why not:

inversions = inversion +1

lawrencetecho + 0 comments [deleted]

andras_igneczi + 7 comments I don't realy understand the example. Why do we have to do 4 swaps in case of this array: 2 1 3 1 2? If we swap

a[0] <-> a[3] ==> 1 1 3 2 2, and

a[2] <-> a[4] ==> 1 1 2 2 3,

we can get the sorted array.

JeffLangston + 1 comment What you say is true, but not with the given merge sort algorithm. The point of this lesson is the get a better understanding of merge sort.

pwinward + 3 comments Yes, but the problem description is misleading.

"Given datasets, print the number of inversions that must be swapped to sort each dataset on a new line."

This seems to imply that

- every inversion requires a swap, or
- not every inversion requires a swap, but we should find the minimum number of inversions that do require swaps since "number of inversions that must be swapped" <= "number of inversions"

In reality, it should simply say: "For each dataset, print the number of inversions found in that dataset on a new line."

This problem would be much more clear without any mention of swaps.

mets_dev + 0 comments This is quite true and is terribly misleading.

johncoleman83 + 7 comments Furthermore, the description is misleading because the example from the problem description of

`|2, 1, 3, 1, 2|`

is an example of**isertion sort**, not merge sort.input = [2, 1, 3, 1, 2] swap_1 = [1, 2, 3, 1, 2] swap_2 = [1, 2, 1, 3, 2] swap_3 =[1, 1, 2, 3, 2] swap_4 = [1, 1, 2, 2, 3]

*4 steps -> insertion sort*Merge Sort does not swap, but rather divides the array by 2, recursively (O log(n)), and then creates a new array, each divided part is added one at a time with its complement half, in the correct order (O (n)) Total calculation O(n*log(n)), in this way:

After arrays are divided, they are joined like this:

input = [2, 1, 3, 1, 2] merge_1 = [1, 2, 3, 1, 2] merge_2 = [1, 2, 1, 2, 3] merge_3 = [1, 1, 2, 2, 3]

*3 steps -> merge sort*Since, this is a merge sort algo, yet, expects the counts to be unrelated to merge sort, I find this to be particularly confusing question.

ernst_maurer + 1 comment what you described is not a merge sort algorithm. seems the author of the task wants two conflicted things: 1. calculate Insert Sort swaps 2. but to provide O(n*log(n)) complexity (use e.g. MergeSort )

is not it?

untitledtitled + 0 comments I was also confused by this.

miguelanrolhor + 0 comments I think that the point is that you can only swap adjacent elements

hotshot47 + 2 comments I don't understand how this problem is a mergesort. It is more of a bubblesort, as it is doing adjacent element swaps if not in order. For mergesort, while merging two halves, we compare the numbers at any given index and pick the lowest number to reconstruct the array. Which is not a swap operation explained in the problem statement. I understand mergesort has better runtime but the problem is confusing and conflicting.

miguel_rivero_p1 + 1 comment I agree. I don't see how you can come out with using merge sort for this problem unless you already knew it beforehand.

samlee405 + 0 comments Right, I understand it now that I've done some reading, I just don't get how someone would make the immediate leap to implement mergeSort for this problem

hungerfordj + 0 comments A merge sort is useful because: 1) it is faster than a bubble sort, but 2) if you

*did*perform the merge sort by swapping adjacent elements rather than copying to a second array, you would never swap any adjacent elements that weren't inverted. A merge sort, thus modified, would use the same number of swaps as a bubble sort that avoided non-inverted swaps by bringing down elements in ascending order (say, by using a map).The key to the problem is that it is easy to perform an actual (and therefore fast) merge sort while calculating how many swaps you

*would*have done to get each transformation.

weeebox + 5 comments A great explanation by Tim Roughgarden can be found on Coursera: https://www.coursera.org/learn/algorithm-design-analysis

Check: Week 1, O(n log n) Algorithm for Counting Inversions I, II

We can avoid allocating and copying multiple arrays by using a single

`aux`

array of size`n`

(where`n`

is the size of the original array). Both arrays are switched on each recursive call.import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { private static long countInversions(int[] arr) { int[] aux = arr.clone(); return countInversions(arr, 0, arr.length - 1, aux); } private static long countInversions(int[] arr, int lo, int hi, int[] aux) { if (lo >= hi) return 0; int mid = lo + (hi - lo) / 2; long count = 0; count += countInversions(aux, lo, mid, arr); count += countInversions(aux, mid + 1, hi, arr); count += merge(arr, lo, mid, hi, aux); return count; } private static long merge(int[] arr, int lo, int mid, int hi, int[] aux) { long count = 0; int i = lo, j = mid + 1, k = lo; while (i <= mid || j <= hi) { if (i > mid) { arr[k++] = aux[j++]; } else if (j > hi) { arr[k++] = aux[i++]; } else if (aux[i] <= aux[j]) { arr[k++] = aux[i++]; } else { arr[k++] = aux[j++]; count += mid + 1 - i; } } return count; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int arr[] = new int[n]; for(int arr_i=0; arr_i < n; arr_i++){ arr[arr_i] = in.nextInt(); } System.out.println(countInversions(arr)); } } }

ThatNiceGuy + 2 comments I have two questions related to your answer.

How did you find the logic to calcuate the value of count? Is there someplace I can read about it more?

count += mid + 1 - i;

Second. I made a mistake of swapping aux and arr in the following code based on the function definition and I was getting my answer wrong. Why are you switching? What is the reasoning behind it?

count += countInversions(aux, lo, mid, arr); count += countInversions(aux, mid + 1, hi, arr);

weeebox + 4 comments Hey there!

1) Check Tim Roughgarden's lecture: he has a really good explanation about incrementing the total count.

2) Swapping the original and the aux array saves you an extra "copying" step each time you make a merge: take a small example and run the algorithm manually to see how it works.piyush121 + 3 comments The only tricky part here is how to merge two sorted arrays. Here is my similar solution. Might be slightly easier to understand because of less number of arguments. Though, I recommend to think as much as you can before looking into the solution. :

public static long countInversions(int[] arr){ return mergeSort(arr, 0, arr.length - 1); } public static long mergeSort(int[] arr, int start, int end){ if(start == end) return 0; int mid = (start + end) / 2; long count = 0; count += mergeSort(arr, start, mid); //left inversions count += mergeSort(arr, mid + 1, end);//right inversions count += merge(arr, start, end); // split inversions. return count; } public static long merge(int[] arr, int start, int end){ int mid = (start + end) / 2; int[] newArr = new int[end - start + 1]; int curr = 0; int i = start; int j = mid + 1; long count = 0; while(i <= mid && j <=end) { if(arr[i] > arr[j]) { newArr[curr++] = arr[j++]; count += mid - i + 1; // Tricky part. } else newArr[curr++] = arr[i++]; } // Leftover elements here. while(i <= mid) { newArr[curr++] = arr[i++]; } while(j <= end) { newArr[curr++] = arr[j++]; } System.arraycopy(newArr, 0, arr, start, end - start + 1); // Usual stuff from merge sort algorithm with arrays. return count; }

Paul_Denton + 1 comment I did this course some time ago, but now I cannot find it anymore :( Does anyone know where I can get the course material from?

ritikranjan825 + 0 comments thanks a lot it really helped. this guys lecture was really good.

lk00100100 + 3 comments Let's take: 2 1 3 1 2 This splits to: 2 1 3 / 1 2 Left Side: 2 1 3 Next: 2 1 / 3 Next: 2 / 1. Recombining this is 1 2 (Now, INV is now 1). Next: 3 is 3. Back to: 1 2 / 3. Recombining this is 1 2 3 Now, back to the Right side of 2 1 3 1 2: Right Side: 1 2 Next: 1 / 2 Next: 1 is 1. Next: 2 is 2. Back to: 1 / 2. Recombine for 1 2 Back to the top. We have: 1 2 3 / 1 2, INV = 1

The key here is, "Whenever we pick a number from the right array because it is smaller than the left array, then we have to add to the inversions. How many? The length of the remainder of the left array." So for example, let us recombine these two arrays step by step by comparing the smallest elements of each:

1 2 3 / 1 2 1 <= 1 -> 2 3 / 1 2 2 > 1 -> 2 3 / 2

(1 is less than 2 and 3 from the left array remainder. We add 2 (the length of the left array remainder). INV += 2; INV is now 3)

2 <= 2 - > 3 / 2 3 < 2 -> 3

(2 is less than 3 from the left array remainder. We add 1 (the length of the left array remainder). INV += 1; INV is now 4)

3 -> done

count += mid + 1 - i;

This adds the length of the remainder of the left array to the count.

codexceed + 1 comment Can anyone help with this? I'm getting output 5 where I should get 4 in the 2nd sample.

long long merge(vector<int> arr, int l, int h){ int aux[h-l+1]; int mid = (l+h)/2; int i=l, j=mid+1, k=0, count=0; while(i<=mid&&j<=h){ if(arr[j]<arr[i]){ aux[k] = arr[j]; j++; count+=mid-i+1; } else{ aux[k] = arr[i]; i++; } k++; } while(i<=mid){ aux[k] = arr[i]; i++; k++; } while(j<=h){ aux[k] = arr[j]; j++; k++; } k=0; for(int x=l;x<=h;x++){ arr[x] = aux[k]; k++; } return count; } long long mergeSort(vector<int> arr, int lo, int hi){ if(lo>=hi) return 0; int mid = (lo+hi)/2, count=0; count+=mergeSort(arr, lo, mid); count+=mergeSort(arr, mid+1, hi); count+=merge(arr, lo, hi); return count; } long long count_inversions(vector<int> a) { return mergeSort(a, 0, a.size()-1); }

davidnhnd + 0 comments Thanks for your help. saved my day

richard2957 + 0 comments Whenever we pick a number from the right array because it is smaller than the left array, then we have to add to the inversions. How many? The length of the remainder of the left array."

Thanks, that gave the answer away! So basically a straightforward merge sort with that extra line.

Here's my answer in javascript

// Complete the countInversions function below. function countInversions(arr) { let count=0; mergesort(arr) function mergesort(myar){ if (myar.length==1) return myar; let mid= Math.floor(myar.length/2); const a1= mergesort(myar.slice(0,mid)); const a2= mergesort(myar.slice(mid)); return merge(a1,a2); } function merge(a1,a2){ let ptrA=0; let ptrB=0; const NewArr=[]; while ((ptrA <a1.length) && (ptrB < a2.length)){ if (a1[ptrA] <= a2[ptrB]){ NewArr.push(a1[ptrA]); ptrA++ } else { NewArr.push(a2[ptrB]); ptrB++ // and here's the extra line to get the count count=count + (a1.length-ptrA) }} for (let i=ptrA; i<a1.length;i++){NewArr.push(a1[i])} for (let i=ptrB; i<a2.length;i++){NewArr.push(a2[i])} return NewArr

}

return count;

}

leontd + 0 comments Just ran a similar implementation of this, and there seems to be a number of test cases failure. Perhaps, they've updated with more test cases since this was posted.

edrouwendaal + 0 comments [deleted]

Sort 374 Discussions, By:

Please Login in order to post a comment