Answer 1-7

Exercise 2: sorting algorithms, correctness and runtime (44 points). Consider an algorithm INSERTION-MERGE-SORT with the followingp INSERTION-MERGE-SORT(A,p,r) 1 ifp key Ali Al 6 Ali t 11-ket, 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. Iint: 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. 5. (5 points) Imagine that the partition in INSERTION-MERGE-SORT in two subarrays is 0, instead of Gn, jn). Give the recurrence and its runtime again (consider only the best case) 6. (4 points) Is INSERTION-MERGE better than MERGE? Is INSERTION-MERGE-SORT better than y for each case INSERTION-SORT or MERGE-SORT? Con sider the complexity in time and memor 7. (9 points) Give the pseudocode for an algorithm SELECTION-MERGE-SORT A, p, r) that modi fics 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 followingp INSERTION-MERGE-SORT(A,p,r) 1 ifp key Ali Al 6 Ali t 11-ket, 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. Iint: 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. 5. (5 points) Imagine that the partition in INSERTION-MERGE-SORT in two subarrays is 0, instead of Gn, jn). Give the recurrence and its runtime again (consider only the best case) 6. (4 points) Is INSERTION-MERGE better than MERGE? Is INSERTION-MERGE-SORT better than y for each case INSERTION-SORT or MERGE-SORT? Con sider the complexity in time and memor 7. (9 points) Give the pseudocode for an algorithm SELECTION-MERGE-SORT A, p, r) that modi fics 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