Insertion-Merge-Sort(A, p, r) if p key A[i+1] = A[i] i=j-1 A[i+1] = key Merge (A
ID: 441877 • Letter: I
Question
Insertion-Merge-Sort(A, p, r) if p key A[i+1] = A[i] i=j-1 A[i+1] = key Merge (A, p, q, r) n1 = q-p+1 n2 = r-q let L[1..n1 +1] and R[1..n2 + 1] be new arrays for i =1 to n1 L[i] = A[p+i-1] for j = 1 to n2 R[j] = A[q + j] L[n1+1] = infinity R[n2 +1] = infinity i = 1 j = 1 for k = p to r if L[i] R[j] A[k] = L[i] I = i+1 else A[k] = R[j] j = j+1 Prove that INSERTIONMERGE solves the same problem as the MERGE algorithm but works in place. Hint: use a loop invariant. Prove that INSERTION-MERGE-SORT sorts the input array A. Hint: use induction. Identify the best and worst case of INSERTIONMERGE mid compute the runtime T(n) in asymptotic notation for each. Be explicit about summing the number of iterations in the loops.Explanation / Answer
MERGE (A, p, q, r ) 1. n1 ? q ? p + 1 2. n2 ? r ? q 3. Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1] 4. FOR i ? 1 TO n1 5. DO L[i] ? A[p + i ? 1] 6. FOR j ? 1 TO n2 7. DO R[j] ? A[q + j ] 8. L[n1 + 1] ? ? 9. R[n2 + 1] ? ? 10. i ? 1 11. j ? 1 12. FOR k ? p TO r 13. DO IF L[i ] ? R[ j] 14. THEN A[k] ? L[i] 15. i ? i + 1 16. ELSE A[k] ? R[j] 17. j ? j + 1