Help on #7

Exercise 2: sorting algorithms, correctness and runtime (44 points). Consider an algorithm INSERTION-MERGE-SORT with the following INSERTION-MERGE-SORT(A, p,r) 1 ifpkey A[i + 1]-6] 6 A[i + 1] = key 1. (9 points) Prove that INSERTIONMERGE solves the same problem as the MERGE algorithm of p. 30-31 in the textbook but works in place. Hint: use a loop invariant. 2. (3 points) Prove that INSERTION-MERGE-SORT sorts the input array A. Hint: use induction 3. (6 points) Identify the best and worst case of INSERTIONMERGE and compute the runtime T(n) in asymptotic notation for each. Be explicit about summing the number of iterations in the loops. 4. (8 points) Identify the best and worst case of INSERTION-MERGE-SORT and compute the runtime T(n) in asymptotic notation for each. Give the recurrence explicitly for each instead of (Gve the recurrence and its runtime again (consider only the best case INSERTION-SORT or MERGE-SORT? Consider the complexity in time 5. (5 points) Imagine that the partition in INSERTION-MERGE-SORT in two subarrays is 6. (4 points) Is INSERTION-MERGE better than MERGE? Is INSERTION-MERGE-SORT better than and memory for each case 7. (9 points) Give the pseudocode for an algorithm SELECTION-MERGE-SORT(A, p,r) that modi fies SELECTION-SORT(A) (exercise 2.2-2) in the same way as INSERTION-MERGE-SORT modified INSERTION-SORT, so that it can merge two sorted arrays. Identify its best and worst case and compute the runtime T(n) in asymptotic notation for each. Based on this, would this improve over INSERTION-MERGE-SORT? Explain. Exercise 2: sorting algorithms, correctness and runtime (44 points). Consider an algorithm INSERTION-MERGE-SORT with the following INSERTION-MERGE-SORT(A, p,r) 1 ifpkey A[i + 1]-6] 6 A[i + 1] = key 1. (9 points) Prove that INSERTIONMERGE solves the same problem as the MERGE algorithm of p. 30-31 in the textbook but works in place. Hint: use a loop invariant. 2. (3 points) Prove that INSERTION-MERGE-SORT sorts the input array A. Hint: use induction 3. (6 points) Identify the best and worst case of INSERTIONMERGE and compute the runtime T(n) in asymptotic notation for each. Be explicit about summing the number of iterations in the loops. 4. (8 points) Identify the best and worst case of INSERTION-MERGE-SORT and compute the runtime T(n) in asymptotic notation for each. Give the recurrence explicitly for each instead of (Gve the recurrence and its runtime again (consider only the best case INSERTION-SORT or MERGE-SORT? Consider the complexity in time 5. (5 points) Imagine that the partition in INSERTION-MERGE-SORT in two subarrays is 6. (4 points) Is INSERTION-MERGE better than MERGE? Is INSERTION-MERGE-SORT better than and memory for each case 7. (9 points) Give the pseudocode for an algorithm SELECTION-MERGE-SORT(A, p,r) that modi fies SELECTION-SORT(A) (exercise 2.2-2) in the same way as INSERTION-MERGE-SORT modified INSERTION-SORT, so that it can merge two sorted arrays. Identify its best and worst case and compute the runtime T(n) in asymptotic notation for each. Based on this, would this improve over INSERTION-MERGE-SORT? Explain