# Merge Sort: Counting Inversions

# Merge Sort: Counting Inversions

RachelAF + 13 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 + 0 comments Wish this comment had been higher up. It would have saved me a good bit of time.

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...

dominichul2 + 0 comments I saw this comment before solving. Finished the solution, spent 3 hours trying to figure out what was wrong and was convinced that I was using long. I wasn't.

sujunzhu + 0 comments Save my life of debugging :) Omg wish I've seen it earlier

wasaequreshi + 0 comments Literally I read the first part of this post and realized what I was doing wrong. Thank you so much! :)

chava_jauregui + 0 comments [deleted]gurpreetmann + 0 comments Thanks you made my life much easier.

raajtilaksarma + 0 comments [deleted]vasilij_kolomie1 + 0 comments Thx, but in Python it does not matter ))

krspv + 0 comments I wish I saw the discussion before I spent hacker points to reveal a wrong answer only to find out I needed to use long instead of int for the swap counter

isabelladom247 + 0 comments Sorting is a method that is used for ordering some list of elements. There are different types of sorting is useful. Merg sorting is one method of sorting. The given method is making the sorting is very much easier Gokarna Resort .

flying_flyier + 0 comments THANKS

djv + 28 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 + 0 comments 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 + 2 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 + 2 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.

manjiri_mg + 2 comments My timeouts - Python3 - (test11, 12, 13) went away by replacing len(array) with variable.

coder1033 + 0 comments [deleted]coder1033 + 0 comments Passed all the test cases in

**Python 3**. Don't use .append/slicing/len()def merge(a,n1,index1,n2,index2,b,index,count): while n1!=0 and n2!=0: if a[index1]<=a[index2]: b[index]=a[index1] index+=1 index1+=1 n1-=1 else: b[index]=a[index2] index+=1 index2+=1 n2-=1 count+=n1 while n1!=0: b[index]=a[index1] index+=1 index1+=1 n1-=1 while n2!=0: b[index]=a[index2] index+=1 index2+=1 n2-=1 return count,b def mergepass(a,n,l,b,count): q=int(n/(2*l)) # total no. of pairs present s=2*l*q # total no. of elements that are in pairs r=n-s #total no. of elements remaining without making any pair for i in range(q): lb=2*i*l #lowerbound count,b = merge(a,l,lb,l,lb+l,b,lb,count) if r<=l: for i in range(r): b[s+i]=a[s+i] else: count,b = merge(a,l,s,r-l,s+l,b,s,count) return count,b def countInversions(a,n): l=1 count=0 while l<n: b=[0]*n count,b=mergepass(a,n,l,b,count) a=[0]*n count,a=mergepass(b,n,l*2,a,count) l=4*l return count

assumptionsoup + 0 comments len() is constant time, but arr0[i0:] is copying the array first which is what slows things down

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

lawrencetecho + 0 comments [deleted]lifehacker1612 + 0 comments hey @episodeyang..when i try to initialize inversions as a global variable and then increment it during the calls to merge..i'm getting wrong answer it maybe a complete noobie mistake..help me out!!

meg_mitchell + 1 comment None of the Python versions worked for my last 3 test cases, PyPy was even worse with timeouts. Ended up rewriting in C#.

danielgomezrico + 0 comments you were creating the temp array inside of each merge? that may end in creating a lot of arrays and if cases are big then it takes more time to allocate/dealloc that memory.

what do you think?

nimbus2001 + 0 comments Thanks! I spent an agonizing half hour trying to fifure this out before stumbling onto your comment.

phillipnguyen + 0 comments The key to avoiding timeouts with Python is to make sure that your merge function doesn't use del or list.pop(0) which is O(n). Instead iterate through the arrays with indices (or alternatively merge the arrays from back to front).

neadam9 + 0 comments Amazing, thanks! Passed right away in pypy3

anibal2082 + 0 comments Thank you, switched to pypy3 from python 3 and it worked!

eslamsamymeg + 0 comments great advice man, Thanks :)

wezley + 0 comments Thanks...

laszlo_blanar + 1 comment I could pass all the test cases with Python 3, after I eliminated the dots in the loops. E.g. append = arr.append.

prakashaditya + 1 comment Can you explain what do you mean by this, please?

laszlo_blanar + 0 comments Sorry, prakashaditya, I missed your question...

Here comes the explanation: https://wiki.python.org/moin/PythonSpeed#Take_advantage_of_interpreter_optimizations

jahaniam + 0 comments nice!thanks

wknb1996 + 0 comments Wow, glad I looked at the discussion! Thank you!

SergeyM + 0 comments Great! Switching from Python 3 to Pypy 3 works for me also!

anthonyquivers + 0 comments WOOO!!! Super fast!

CoderIlluminatus + 4 comments I have eliminated all len() and pop() calls from the loops and it manages to pass all the test cases in Python 3.

def merge(arr, left_half, right_half): i, j, k = 0, 0, 0 inversions = 0 left_len, right_len = len(left_half), len(right_half) while i < left_len and j < right_len: if left_half[i] <= right_half[j]: arr[k] = left_half[i] i += 1 else: arr[k] = right_half[j] j += 1 inversions += left_len - i k += 1 while i < left_len: arr[k] = left_half[i] i, k = i+1, k+1 while j < right_len: arr[k] = right_half[j] j, k = j+1, k+1 return inversions def merge_sort(arr): if len(arr) > 1: mid = len(arr)//2 left_half, right_half = arr[:mid], arr[mid:] inversions = merge_sort(left_half) + merge_sort(right_half) + merge(arr, left_half, right_half) return inversions return 0 def countInversions(arr): return merge_sort(arr) if __name__ == "__main__": t = int(input().strip()) for a0 in range(t): n = int(input().strip()) arr = list(map(int, input().strip().split(' '))) print(countInversions(arr))

billchenxi + 0 comments Not working for testcase 13

shikhin_arora + 0 comments For me also removing unnecessary len() calls made it work on python 2.

def countInversions(arr): mergeSort(arr) return count

def mergeSort(arr): if len(arr) == 1: return arr else: mid = len(arr)/2 return merge(mergeSort(arr[:mid]), mergeSort(arr[mid:]))

def merge(a1, a2): comb = []

`i, j, k = 0, 0, 0 la1 = len(a1) la2 = len(a2) while i < la1 and j < la2: elemA = a1[i] elemB = a2[j] if elemA > elemB: comb.append(elemB) j += 1 global count count += la1 - i else: comb.append(elemA) i += 1 while i < la1: comb.append(a1[i]) i += 1 while j < la2: comb.append(a2[j]) j += 1 return comb`

prratek_95 + 2 comments Why should right_half start from mid and not mid+1? I had a similar implementation but with it starting from mid+1 and I got all the sample test cases wrong. My thinking was that if you start from mid the last element of left_half and first of right_half would be the same, which wouldn't make sense.

shikhin_arora + 0 comments Because we have already compared with mid. If you are checking the left and right sub arrays, this means that mid is definitely not our answer. So we can skip it

CoderIlluminatus + 0 comments `left_half`

ends at`mid - 1`

. No elements are common between the left and the right halves.

Pick_A_Username + 0 comments I tried pop (O(N)), deque (time to change list to deque and maybe change back), del(O(N)), none of them can pass 11, 12, 13. Finally, by this hint, get rid of array manipulation (pure pointer changing) get all tests passed. Thanks!

Persistencia + 0 comments My implementation in Python of tutorial's Java version:

def countInversions(arr): res = [0] * len(arr) return merge(arr, res, 0, len(arr)-1) def merge(arr, res, left, right): if left >= right: return 0 inversions = 0 left_end = (left + right) // 2 right_start = left_end + 1 inversions += merge(arr, res, left, left_end) inversions += merge(arr, res, right_start, right) inversions += mergeHalf(arr, res, left, right) return inversions def mergeHalf(arr, res, left, right): if left >= right: return 0 inversions = 0 left_end = mid = (left + right) // 2 right_start = right_beg = left_end + 1 left_beg = index = left while left <= left_end and right_start <= right: pt1 = arr[left] pt2 = arr[right_start] if pt1 <= pt2: res[index] = pt1 index += 1 left += 1 else: res[index] = pt2 index += 1 inversions += mid - left + 1 right_start += 1 while left <= left_end: res[index] = arr[left] left += 1 index += 1 while right_start <= right: res[index] = arr[right_start] right_start += 1 index += 1 arr[left_beg:left_end + 1] = res[left_beg:left_end + 1] arr[right_beg:right + 1] = res[right_beg: right + 1] return inversions

hellomici + 0 comments So true! Thanks a lot :)

Here is my code is you feel like reviewing it:

(By Merge_and_CountSplitInv(): - :param left_half: sorted list C - :param right_half: sorted list D - :return: sorted list B (length n) and the number of split inversions)

def Merge_and_CountSplitInv(left_half, right_half): i = 0 j = 0 splitInv = 0 B = [] while i < len(left_half) and j < len(right_half): if left_half[i] <= right_half[j]: B.append(left_half[i]) i += 1 else: B.append(right_half[j]) j += 1 splitInv += (len(left_half) - i) B += left_half[i:] B += right_half[j:] return B, splitInv def Sort_and_CountInv(A): # base case if len(A) < 2: return A, 0 # divide the list into two mid = len(A) // 2 left = A[:mid] # recursively sort first half of A right = A[mid:] # recursively sort second half of A x, leftInv = Sort_and_CountInv(left) y, rightInv = Sort_and_CountInv(right) z, splitInv = Merge_and_CountSplitInv(x, y) return z, leftInv + rightInv + splitInv

eduardocorral + 0 comments Same here: three of the cases timeout out in Python 2/3 and PyPy 3.

Another poster had a full solution in Python, stating that was working, same general mergesort implementation. I profiled both with cProfile, and measured total time, and both solutions where within 100 ms for Case 11.

I used a single (two, counting input) array allocation, and pivots, and still couldn't make it work. No append, no recursive len(). Don't know where else I could save time.

razorstacks123 + 1 comment calculating "len(whatever)" in the beginning of the function and carrying the variable through the function should be plenty to save time... it worked for me at least.

Lherbeur + 1 comment I don't quite get that. I'm declaring the array just once and passing it into the recursive merge, so I don't always have to recreate the array for every merge.

razorstacks123 + 1 comment I was having problems in Python 3 where I would keep calling len() to get the length of my current array for each loop I was doing. When I initialized two variables with "l = len(left)" and "r = len(right)" at the beginning of my merging function, the time seemed to reduce enough to pass all test cases. Here is what I mean by that:

def merge(left, right, inversions): new = [] i = j = 0 if left == None: left = [] if right == None: right = [] l = len(left)#!!!!!!!!! r = len(right)#!!!!!!!!

`while i < l and j < r: #before while i < len(left) and j < len(right) if left[i] <= right[j]: new.append(left[i]) i += 1 else: inversions[0] += (l - i) new.append(right[j]) j += 1 while i < l: #before: while i < len(left) new.append(left[i]) i += 1 while j < r: #before: while j < len(right) new.append(right[j]) j += 1 return new`

Previously, when I was using "while i < len(left) and j < len(right)", "while i < len(left)" and "while j < len(right) " the program would not pass all test casses (although, I wouldn't think the len() function actually takes that long).

Hope this clarified my post.

Lherbeur + 1 comment Oh Ok. Yea. My own challenge, though is that it still fails in Java, despite not recreating the array on each merge. Do you have an idea what might be wrong? That's if you understand Java.

// 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; } 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; } System.out.printf("Dataset %d \n", tItr); long result = countInversions(arr); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); } bufferedWriter.close(); scanner.close(); }`

razorstacks123 + 2 comments The code you provided me passes all tests in Java 8... I just cut and pasted it in and it is working fine, with no modifications.

Are you experiencing time-outs?

Lherbeur + 0 comments Really? That's weird cos it kept giving me timeouts on some cases. Tried it just now again and all passed. It's really weird though cos I tried it repeatedly. Anyway, thanks for the time!

Lherbeur + 0 comments Could it be that the grader was overloaded for some reason? Probably the reason for the timeout.

lwchkg + 0 comments Not all O(n log n) solutions will pass. Here is one example that fails (locality of reference does matter):

long countInversions(vector<int> arr) { long inversions = 0; const int bits = 24; vector<unordered_map<int, long>> counts(bits); for (auto iter = arr.crbegin(); iter < arr.crend(); iter++) { int item = *iter; // Read counts. { // scope int copy = item; for (int shifted = 0; shifted < bits; ++shifted) { if ((copy & 1) > 0) inversions += counts[shifted][copy - 1]; copy >>= 1; } } // Add to counts. { // scope int copy = item; for (int shifted = 0; shifted < bits; ++shifted) { counts[shifted][copy]++; copy >>= 1; } } } return inversions; }

winnochan + 0 comments Thank you very much!!!

miguel_t + 0 comments [deleted]luckyy1298 + 0 comments Your comment saved hours of my time! Thank you! I wonder why it doesn't work on python 3

eduasinco + 0 comments This is so dumb, thank you!

EmadHosseini + 0 comments You sir, saved my 2 days of effort to improve on mathematically impossible algorithm. This challenge ceratinly have flaw since I have perfected my code in Python 3

jordisoler + 0 comments A quite simple Python approach that times out in 3 test cases:

from bisect import bisect_right, insort # Complete the countInversions function below. def countInversions(arr): inversions = len(arr)*(len(arr)-1)//2 left = [] for idx, v in enumerate(arr): v_idx = bisect_right(left, v) inversions -= v_idx insort(left, v) return inversions

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.

recodeFuture + 0 comments I agree, the problem definition and results don't match. I was surprised when my solution didn't work. I solved it by adding the distance of the swap instead of incrementing just by 1.

khris_kooper + 0 comments I wondered why I kept getting 3 for this case!

edvardpitka + 2 comments I agree, I counted only times when right was greater than left, and although I would get sorted array, number of swaps did not match.

aarish + 0 comments Same issue. Very misleading problem. So did you guys change it to insertion sort counting of swaps to make it work ?

Ocelotl + 0 comments I seem to have the same issue. Funny thing is that the editorial solution says I should implement precisely what I have implemented. For the example [2, 1, 3, 1, 2], merge sort does

**exactly**the same swaps as the ones that are done in the problem example.Nevertheless, this is failing almost every test case, even when the sorting seems to be working fine.

swap_counter = 0 def merge_sort(list_): if len(list_) == 1: return list_ middle = len(list_) // 2 left_list = list_[0:middle] right_list = list_[middle:len(list_)] left_list = merge_sort(left_list) right_list = merge_sort(right_list) sorted_list = [] left_list_index = 0 right_list_index = 0 while ( left_list_index < len(left_list) ) or ( right_list_index < len(right_list) ): if left_list_index == len(left_list): sorted_list.append(right_list[right_list_index]) right_list_index += 1 elif right_list_index == len(right_list): sorted_list.append(left_list[left_list_index]) left_list_index += 1 elif left_list[left_list_index] <= right_list[right_list_index]: sorted_list.append(left_list[left_list_index]) left_list_index += 1 else: global swap_counter swap_counter += 1 sorted_list.append(right_list[right_list_index]) right_list_index += 1 return sorted_list for _ in range(int(input().strip())): swap_counter = 0 input() merge_sort(list(map(int, input().strip().split()))) print(swap_counter) swap_counter = 0 merge_sort([1, 1, 1, 2, 2]) assert swap_counter == 0 swap_counter = 0 merge_sort([2, 1, 3, 1, 2]) assert swap_counter == 4, swap_counter sorted_ = merge_sort([4, 5, 1, 8]) assert sorted_ == [1, 4, 5, 8], sorted_ sorted_ = merge_sort([5, 4, 1, 8]) assert sorted_ == [1, 4, 5, 8], sorted_ sorted_ = merge_sort([5, 4, 8, 1]) assert sorted_ == [1, 4, 5, 8], sorted_ sorted_ = merge_sort([5, 4, 8, 1, 3]) assert sorted_ == [1, 3, 4, 5, 8], sorted_

pierce_hubbard_1 + 0 comments I spent days banging my head on my desk a year ago trying to solve this, and finally gave up. Tonight I decided to try and tackle it again, and kept getting 3 swaps for this same test case, and I couldn't understand what I was doing wrong because I was returning a perfectly sorted array. Then I read your comment. Thank you!!!

barcellos_marcio + 0 comments [deleted]saeed_afroozi + 0 comments dear Your are right but when I test your solution it didn't pass some test cases due to time out.Do you have any Idea what can I do?

bonnotguillaume + 0 comments The description of the problem is quit terrible.

Basically, you need to implement a merge sort and add a counter.

This counter is incremented when you merge, everytime you copy from the right part of the buffer, the number of swaps will be this :

swaps += int64(mid + 1 - left)

where left is the current index you use to keep track of which values from the left buffer where copied in the array

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?

johncoleman83 + 0 comments Yes, it appears the question is to calculate the number of insertion sort swaps with O(n*log(n)) time complexity, but this is not explained well at all and the automated answers do not except this type of answer. This was my first algo, but then after realizing how poorly designed the question is, I moved on.

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

carlosmartinezt + 0 comments It says: "we can swap adjacent elements" I suppose this means only adjancent elements.

AayushGautam + 0 comments We have to swap only adjacant elements

lars1607 + 0 comments [deleted]davidgsawyer + 0 comments I read this part of the description "we can swap adjacent elements" to mean that swaps can only be a distance of 1. So 2 1 3 1 2 requires the 3 to move 2 times backwards and the front 2 to move back 2 spots. for a total of 4 moves. In fact, I solved it the "wrong" way by counting and summing the number of elements found so far that are larger then arr[i]. That is adding up 0, 1, 0, 2, 1 for the number of elements to the left that are greater. Also O (n log n)

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; }

prajwalrhegde + 1 comment Could you please explain me how can we get count by this line of code ??

count += mid - i + 1;

piyush121 + 4 comments Consider following case for split inversion : 1 3 5 6 | 2 4 7

These two are sorted sub-arrays. When you merge them

`1`

will need no inversions but 2 will have to invert all of`3 5 6`

to reach to its appropriate place. if you think deeply enough you will realize that it is in fact the case.prajwalrhegde + 0 comments Thank you so much Piyush :)

kutaykalkan + 0 comments Hey bud you nailed it. I kept looking for a way to understand how to approach this. I kept trying Math.Abs(i - j) and getting close but not the exact count. Thumbs up :)

jorgekasa + 0 comments This is a great explanation by

**Tim Roughgarder**about this algorithm and why this formula works:count += mid - i + 1;

saeed_afroozi + 0 comments Dear Could you tell me where i should count in this code by javascript Thanks.

`function mergeSort(arr) { if (arr.length === 1) return arr; var middle = Math.floor(arr.length / 2); var left = arr.slice(0, middle); var right = arr.slice(middle, arr.length); return merge(mergeSort(left),mergeSort(right)); } function merge(left, right) { var indexLeft = 0; var indexRight = 0; var result = []; while (indexLeft < left.length && indexRight < right.length) { if (left[indexLeft] < right[indexRight]) { result.push(left[indexLeft]); indexLeft++; } else { result.push(right[indexRight]) indexRight++; } } return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight)); }`

Adil_Muthukoya + 0 comments Dude how come you guys are thinking this sort of solutions. Hats off..... First of all in a recursive algo its very difficult for me to assume the values of each var in whole iterations. Keeping in mind you created an equation for number to be added in each iterations to count... great.....

shjang + 0 comments Yes.. that was tricky part of it. To counting the swap, and definition type into long type. Thank you it was helpful.

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?

Romana + 0 comments

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

ritikranjan825 + 0 comments can you explain how swaping the aux array saves extra time;

lk00100100 + 2 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); }

codexceed + 1 comment Nevermind, figured it out.

srizify + 1 comment i'm also getting the same problem.how did you correct it?

codexceed + 1 comment I believe it has something to do with declaring paramter in functions as vector as '&vec' rather than just 'vec'. Can't remember for certain. Also, you might wanna declare the count variable as long long for larger data sets.

srizify + 0 comments i used '&vec'.that solved the problem.thanks buddy!

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

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]andikadevs + 0 comments You're pro sir. So, the key about this problem is not creating many arrays

deankiss + 0 comments dats tight

safaogluozum + 2 comments I don't understand the requirement in this problem. Are we supposed to make the minimum number of swaps ? Question seems to be expecting us to use the principle of merge sort, however merge sort does not guarantee minimum number of swaps.

ericgtx + 0 comments Apparently it does. I believe this is because merge sort is stable (no unnecessary swaps of equal elements). Why do you think merge sort does not guarantee a minimum number of swaps?

hungerfordj + 0 comments If I understand this correctly, the merge sort is needed to complete the sorting without timing out. In fact, a merge sort

*cannot*technically be used to perform the sorting demanded by the problem, since a merge sort does not swap adjacent elements. In the course of performing a merge swap, however, it is not difficult to calculate the number of such swaps that would be needed to achieve each transformation of the array.

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.

feature_dragon + 4 comments This passed using Python 3. I had to add an alias to the

`list.append`

function to get it to work.def merge(a1, a2): swaps, i, j, result, m, n = 0, 0, 0, [], len(a1), len(a2) ra = result.append while i < m and j < n: if a1[i] <= a2[j]: ra(a1[i]) i += 1 else: ra(a2[j]) j += 1 swaps += m - i result += a1[i:] result += a2[j:] return swaps, result def msort(arr): n = len(arr) mid = n // 2 if n > 1: left_swaps, left_result = msort(arr[:mid]) right_swaps, right_result = msort(arr[mid:]) m_swaps, result = merge(left_result, right_result) return m_swaps + left_swaps + right_swaps, result return 0, arr

alexgcuevas + 0 comments What is the purpose of the alias? Why does that prevent timeout?

kit_shukla88 + 0 comments This is by far the most elegant solution i've seen to this problem.

hubrando + 0 comments Looking at other solutions, I think you can save more time by not creating a list, but sorting in place.

c_m_s_gan + 0 comments Hahaha thanks for the tip; couldn't believe that assigning the lengths and the "result.append" method to variables actually sped up the algorithm significantly.

I had a variant with nested functions earlier (merge nested in mergesort, mergesort nested in countInversions) that timed out on more than half of the cases.

So essentially my solution is virtually similar to yours; anyone with a better way apart from tweaking the mergesort boilerplate code to keep track of the number of occurrences?

def merge(left, right): counter = 0 result = [] # final result array, that is an empty array #create two indices and initialize with 0 i,j = 0,0 ra = result.append lenl = len(left) lenr = len(right) # Till this condition is true, keep on appending elements into resultant array while (i<lenl) and (j<lenr): if left[i] <= right[j]: ra(left[i]) #append ith element of left into resultant array i+=1 else: ra(right[j]) #append jth element of right into resultant array j+=1 counter += lenl-i #COUNT HERE! # it is basically specifies that if any element is remaining in the left array from - # ith to the last index so that it should appended into the resultant array. And similar - # to the right array. result += left[i:] result += right[j:] return result, counter # Definition for merge sort # this takes an input list def mergesort(lst): if(len(lst)<= 1): # this means that the list is already sorted. return lst, 0 mid = (len(lst)//2) # Define definition for merge which basically takes two arrays i.e., the left and right part # left array will be mergesort applied over the list from starting index # till the mid index left, counter0 = mergesort(lst[:mid]) # right array will be mergesort applied recursively over the list from mid index # till the last index right, counter1 = mergesort(lst[mid:]) result, counter2 = merge(left,right) return result, counter2 + counter0 + counter1 def countInversions(arr): #Idea: Count the number of transpositions needed when you apply the mergesort to arr. final, counter = mergesort(arr) return counter

DCoy54 + 2 comments Getting all the right solutions but the last 3 tests are timing out (Swift). Just to see, I commented out my actual method call and it's still timing out just reading the larger inputs. This is ridiculously bad on HackerRank's part... What a joke

let _ = readLine() while let _ = readLine() { let array = readLine()!.components(separatedBy: " ").flatMap{Int($0)} //let (_, inversions) = countInversions(array: array) print("0") }

tjkemper6 + 1 comment Same situation with go.

mani_shailesh96 + 0 comments Scaning the array using 'bufio.Scanner' does it.

rhunterharris + 1 comment Same situation with Python3

doktoren + 1 comment Guys use the Scanner class instead of readLine. Its much faster

jonny_mcallister + 0 comments this got me too. Very frustrating. Here is Scanner code that works.

Thanks @doktoren for the lead.

(Credit to Martin R on StackExchange for this code https://codereview.stackexchange.com/users/35991/martin-r)

public func splitToIntegers(_ s: String, count: Int) -> [Int] { var result: [Int] = [] result.reserveCapacity(count) var n = 0 let scanner = Scanner(string: s) while scanner.scanInt(&n) { result.append(n) } return result } let d = Int(readLine()!)! for _ in 0..<d { let length = Int(readLine()!)! let ary = splitToIntegers(readLine()!, count: length) //... }

RodneyShag + 3 comments ### Java solution - passes 100% of test cases

I used MergeSort to count inversions.

Make sure you use a

**long**instead of an**int**to avoid integer overflow.I added a ton of comments below to help explain the code.

import java.util.Scanner; import java.util.Arrays; /* We basically implement MergeSort and 1) Add "swaps" counter and 1 line of code to count swaps when merging 2) Use "long" instead of "int" to avoid integer overflow Runtime: O(n log n) Space Complexity: O(n) */ public class Solution { private static class MergeSort { /* Our array has up to n = 100,000 elements. That means there may be O(n^2) swaps. n^2 is 10,000,000,000. A Java int has max value 2,147,483,647 so we use a long to avoid integer overflow */ private long swaps = 0; public long mergeSort(int [] array) { int [] helper = new int[array.length]; mergeSort(array, helper, 0, array.length - 1); return swaps; } private void mergeSort(int [] array, int [] helper, int start, int end) { if (start < end) { int mid = (start + end) / 2; mergeSort(array, helper, start, mid); mergeSort(array, helper, mid + 1, end); merge(array, helper, start, mid, end); } } private void merge(int [] array, int [] helper, int start, int mid, int end) { /* Fill helper array with same elements as original array */ for (int i = start; i <= end; i++) { // notice "i" goes from "start" to "end", not "0" to "array.length" helper[i] = array[i]; } int curr = start; int left = start; int right = mid + 1; /* Loop through helper[] left and right halves and continuously copy smaller element to array[] */ while (left <= mid && right <= end) { if (helper[left] <= helper[right]) { array[curr++] = helper[left++]; } else { /* Each time we choose element from right side, we count up how many elements it is less than from left side. This is equivalent to counting swaps. */ swaps += mid + 1 - left; array[curr++] = helper[right++]; } } /* Copy remaining elements of left half. Right half elements are already in proper place */ while (left <= mid) { array[curr++] = helper[left++]; } } } 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(); } MergeSort ms = new MergeSort(); System.out.println(ms.mergeSort(arr)); } } }

From my HackerRank Java solutions.

enricogiurin + 0 comments yes, I wasted a lot of time using int, rather than long, a t first :(

aniu1 + 0 comments Beautiful!

yaangliu + 0 comments Good point! There is no sense to use swap to implement merge sort.

kylemart + 2 comments Helpful reference material:

Part 1) https://www.youtube.com/watch?v=yP0asUjcrBA

Part 2) https://www.youtube.com/watch?v=hqeoAIryJOc

The explanation of

`count += mid + 1 - i;`

(seen in below solutions) occurs around the 7:30 minute mark of the second video.jyodroid + 0 comments Good thanks!

greenEkatherine + 1 comment Account was deleted...

srstanic + 0 comments This video explains it also https://youtu.be/k9RQh21KrH8?t=254

Sort 276 Discussions, By:

Please Login in order to post a comment