Counting inversions of 2D pair (x,y) in a list

Question

The question is just like normal counting inversion question, but instead of a list of single numbers, now the input is a list of (x,y) pair.

For a list of pairs [(x1,y1),(x2,y2),(x3,y3),...,(xn,yn)], a pair (i,j) is a inversion iff i < j and xi>xj, yi>yj. Is it possible to write the algorithm in O(nlognlogn)? I tried several ways but during the merge step, each element from the right half of list has to compare with all elements in the left one, resulting in a time complexity of n square.

Answer 1

Split the list into two halves, left and right based on the x coordinate. Then, compare the lowest point of the two halves (based on their y coordinate). There are two cases:

1. The left point is lower than the right point, then the left point has xi<xj and yi<yj for all the points on its right.
2. The right point is lower than left, so the yi>yj condition hold true for any point to its left.
   After updating you answer according to these 2 cases, you can remove one of these two points and continue working on the remaining sorted lists (by recursively solving for left and right as well). This should work in O(nlog^2n)