How to find the number of inversions in an array ?

Question

Possible Duplicate:
Counting inversions in an array

This 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:

1. 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 position j in the sorted copy (binary search) and sum the halves the distances abs(i - j)/2.

2. Modify merge sort : modify merge to count inversions between two sorted arrays and run regular merge sort with that modified merge.

   Does it make sense ? Are there other (maybe simpler) solutions ? Isn't it too hard for a phone interview ?

Solution 1

It is actually an application of divide-and-conquer 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 sub-array, 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 sort-like 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 ith 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.

Comments

[Marek Kirejczyk]

You can find n log n solution coded in java here: stackoverflow.com/questions/337664/…

[huzefa biyawarwala]

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