(18 points) This problem arises in ranking which has many applications especially, in a web technique called collaborative filtering. Here they try to match your preference (for books, movies, restaurants, etc.) with those of other people on the internet. A main problem in collaborative ranking is comparing two rankings. For a list of n movies, say n -4, you rank them as {1,2,3,4} and another person ranks them for example as (3,1,4,23, that is the movie you ranked 1, the other person ranked 4, and so on. A natural way to quantify similarity between two rankings is to count the number of inversions in the second sequence. Suppose the second sequence is (al, a2, an), propose an algorithm in pseudo-code to count the number of inversions with O(n lg n)complexity. (Hint: Recursively divide the list into two sub-lists, count inversions in each sub-list and combine the sub-lists)