What are the advantages / Disadvantages of using binary indexed trees over modified merge sort(or vice versa) for counting inversions in an array ?
advantages of BIT over mergesort is dependent on the elements in array
as in if all elements in an array are unique, then mergesort and BIT works with equal time complexity and space complexity.
but yeah, if this is not the case, then BIT can be more efficient in both time and space complexity by reducing it to (O(log(max element)) and not(O(log(n))
and if you say that if max element is bigger than n or if array is of type
1 5 100 50 100 50 100 we can transform it to 1 2 4 3 4 3 4
so see the difference in time complexity and space complexity :D:D
but transformation can be taken as a disadvantage if its costly for any reason 
2 Likes