Problem 4 (Permutation Pattern Counting)

Assume you are given an array A of unique numbers (i.e. no duplicates). We say that an arbitrary pair of elements in this array, (A[i], A[j]), matches the 2-reversal pattern if i < j and A[i] > A[j].

Using Divide & Conquer, design an O(n lg n) time algorithm that will tell you how many pairs of elements in A match the 2-reversal pattern. Justify its correctness and running time.

Hint: Note that in the the worst case, this could be as many as O(n^2) pairs, so you will need to figure out some way to count the pairs that match this pattern without actually enumerating them. Since you know divide & conquer is the design technique, think inductively like you did with Merge Sort. So start by assuming you have an algorithm that could recusively solve the problem for smaller sub-arrays, and then figure out what additional cases you need to consider to solve the problem for the whole array.