How to find the number of inversions in an array ?
Solution 1
It is actually an application of divideandconquer algorithm, and if you are familiar with it you can come up with the solution quickly.
Take [1 3 8 5 7 2 4 6] as an example, assume we have sorted array as [1 3 5 8] and [2 4 6 7], and now we need to combine the two arrays and get the number of total inversions.
Since we already have number of inversions in each subarray, we only need to find out the number of inversions caused by array merging. Each time an element is inserted, for example, 2 inserted into [1 # 3 5 8], you can know how many inversions there are between the first array and the element 2 (3 pairs in this example). Then you can add them up to get the number of inversions caused by merging.
Solution 2
You could also use a counting sortlike approach, if the array only contains small numbers for example (like if it's a character array):
inversions = 0
let count = array of size array.Length
for i = 0 to array.Length  1 do
for j = array[i] + 1 to maxArrayValue do
inversions = inversions + count[j]
count[array[i]] = count[array[i]] + 1
Basically, keep a count of how many times each element appears. Then at each step i
, the number of inversions the i
th element generates is equal to the sum of all the elements bigger than i
that come before i
, which you can easily compute using the count you're keeping.
This will be O(n*eps)
where eps
is the domain of the elements in your array.
This is definitely simpler in my opinion. As for efficiency, it's only good if eps
is small obviously. If it is, then it should be faster than other approaches since there's no recursion.
Related videos on Youtube
Comments

Michael 15 days
Possible Duplicate:
Counting inversions in an arrayThis is an phone interview question: "Find the number of inversions in an array". I guess they mean O(Nlog N) solution. I believe it cannot be better than O(Nlog N) since this is the sorting complexity.
The answers to a similar question can be summarized as follows:

Calculate half the distance the elements should be moved to sort the array : copy the array and sort the copy. For each element of the original array
a[i]
find it's positionj
in the sorted copy (binary search) and sum the halves the distancesabs(i  j)/2
. 
Modify
merge sort
: modifymerge
to count inversions between two sorted arrays and run regularmerge sort
with that modifiedmerge
.Does it make sense ? Are there other (maybe simpler) solutions ? Isn't it too hard for a phone interview ?

Marek Kirejczyk about 10 yearsYou can find n log n solution coded in java here: stackoverflow.com/questions/337664/…


huzefa biyawarwala over 1 year@ZelluX  How can we solve for array with duplicate values as
[1, 3, 4, 5, 6, 4]
using merge sort ?