Counting inversions in a list of integers using divide and conquer techniques This is a homework. It looks easy, but not really.

A list of integers $a_n$, for every $i&lt;j$, if $a_i&gt;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.
You can do the counting in linear time for each merge step by iterating over the right list and keeping track of the following information regarding the left list:


pointers to the first and last element that formed an inversion with the previous element of the right list
the number of elements between those pointers


Since this is homework, I'll leave it to you to work out the details and analysis.