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

Question

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.

Answer 1

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)$.

Answer 2

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.

Answer 3

THE same problem was discussed by Tim Roughgarden in Coursera algorithms course, see the lecture slides analysis and design of algorithms1 suppose array A = [1, 3, 2, 9,5, 8, 4, 6, 7] split the list into two part using divide and conquer paradigm

count(array A,length n){
  count inversions and then sort
  x=count(1st half of array,n/2);//O(nlogn) count inversions and then sort
  y=count(2nd half of array,n/2);//O(nlogn) count inversions and then sort
  z=countsplitinversions(A,n);//implement this in O(n) time of merging the two sorted lists and count inverions
  return x+y+z;
}

countsplitnversions(array A,length n)
{
  D=output[length=n]
  B=1st sorted array(1st half of array)
  C=2nd sorted array(2nd half of array)
  i=1,j=1
  for k= 1 to n//for merging
    if B[i]<C[j]
      D[k]=B[i];
      i++
    else[C[j]>B[i]]
    D[k]=C[j];
    j++
  end
}

consider [1,3,5] and [2,4,6] so while merging ,due to 2 copied to output there will be 2 inversions(2,3) and (2,5) and when 4 copied to output the split inversion discovered is (4,5)