# How to find the number of inversions in an array ?

29,575

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

Share:
29,575

Author by

### Michael

Scala (moslty) programmer

Updated on May 13, 2022

• Michael 15 days

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 ?

• 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 ?