Insertion-Merge-Sort(A, p, r) if p key A[i+1] = A[i] i=j-1 A[i+1] = key Merge (A

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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.