Counting inversions in a list of integers using divide and conquer techniques

Problem Detail: 

This is a homework. It looks easy, but not really.

A list of integers $a_n$, for every $i<j$, if $a_i>2a_j$, then it is an inversion. Count the inversions in the list, and return the count and the ordered list. Note, here the order is defined by the condition, not just sort the integers.

The easiest way is double loop, but it will be a $O(n^2)$ algorithm. So I think I should try divide and conquer, by modify the merge sort algorithm. I think I could get a $O(n \log n)$ algorithm. But I found, while merging and counting cross-halve inversions, I have to scan all the elements in both left halve and right halve. Equivalent to a double loop.

For example:

[8] [6, 3] 

8 and 6 are not inversion, 6 and 3 are not inversion, but 8 and 3 are inversion. I have scan all the elements to make sure there's no exception.

Another example:

[2, 7] [1, 5] 

There no inversion in either halve, but 7 and 1 are inversion.

I am thinking may be there's a function, and I can define $b_n=f(a_n)$, then I can treat $b_n$ as normal merge sort problem. But I could not figure it out.

Asked By : davidshen84

Answered By : HEKTO

The "Merge and Count" step with more explanations. You have two sorted lists - left one and right one. You need to merge them and concurrently count inversions. I'll be talking about regular inversions, not yours - your job is to extend this description. You have a current position in each list. Initially this position is 0 (the beginning of the list), and it can also point after the end of the list.

• if both current positions are inside their lists, then we have two cases: the left current element is less than the right current element and vice versa. In the first case we just copy the left current element into the resulting list and increment the left position. In the second case we copy the right current element into the resulting list and increment the right position and increment the inversions count by the number of remaining elements in the left list (including the left current element).

• else if there are no left elements anymore, then we append the remaining right list to the resulting list

• else we append the remaining left list to the resulting list

So, sometimes this algorithm adds more than one inversion to the inversions count - this allows it to work faster than $O(n^2)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29519