Question: consider an array that contains two successive copies of the...
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)