[This is problem 4.8 on page 208 in the Baase textbook.]
Consider the following variation of Insertion Sort: For 1<=i<n, to insert an element A[i] among A[0]<=A[1]<=...<=A[i-1], do a Binary Search to find the correct position for A[i].
(a) How many key comparisons are done overall in the worst case?
(b) How many times are elements moved in the worst case?
(c) What is the asymptotic order of the worst-case time complexity?
(d) What happens to the number of comparisons and the number of moves if the elements in the input were stored in a linked list instead of an array? (see question 4 below which is related to this.)
Show the tree of the iterations of the MergeSort algorithm on the following array:
75 45 38 87 99 23 15 67 88 70
How many comparisons are done by MergeSort on an array of size n that is sorted in nondecreasing order? How many moves are done?
Modify the merge procedure that we saw in class to merge two sorted linked lists of integers. Is an auxiliary array necessary for your new procedure?