Consider an array that contains two successive copies of the integers 1 through n, in ascending order. For example, here is the array when n = 4: 1 2 3 4 1 2 3 4

Note that the length of the array is 2n, not n.

How many compares does tops-down Merge sort, Insertion, and Selection sort make to sort the array as a function of n? (for the two sequences in the above example)