Counting inversions in a list of integers using divide and conquer techniques
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.