I need help on this one. I have a hard time to figure out the condition when 2 lines will be crossed along the way when the points are sorted using mergesort. In particular, how will an inversion happen affect the the # of intersection points with reference to 2 list of integers? I assume we will borrow the concept of mergesort and counting inversion for a list of integers to solve this problem. I will be solving this using Java.

Problem:

Suppose you are given two sets of n points, one set {p1, p2, . . . , pn} on the line y = 0 and the other set {q1, q2, . . . , qn} on the line y = 1. Create a set of n line segments by connecting each point pi to the corresponding point qi. Your goal is to develop an algorithm to determine how many pairs of these line segments intersect. Your algorithm should take the 2n points as input, and return the number of intersections. Using divide-and-conquer, you should be able to develop an algorithm that runs in O(n log n) time. Hint: What does this problem have in common with the problem of counting inversions in a list?