Home /
Expert Answers /
Computer Science /
1-16-points-merge-is-an-important-subroutine-for-mergesort-it-is-an-algorithm-that-takes-two-so-pa187
(Solved): 1. (16 points) Merge is an important subroutine for mergesort. It is an algorithm that takes two so ...
1. (16 points) Merge is an important subroutine for mergesort. It is an algorithm that takes two sorted lists and outputs a sorted list of all the elements in the two lists. MERGE([a1,…,ak],[b1,…,bℓ]) 1. i=1 2. j=1 3. output =[] (empty list) 4. while i⩽k and j⩽ℓ : 5. if ai⩽bj : 6. output = output ∘[ai] 7. i=i+1 8. else: 9. output = output ∘[bj] 10. j=j+1 11. if i==k+1 : 12. return output ∘[bj+1,…,bℓ] 13. else: 14. return output ∘[ai+1,…,ak] (a) (5 points) In order to prove the correctness of this algorithm, prove the following loop invariant: After t iterations, output is sorted (b) (5 points) In order to analyze the runtime, prove the following loop invariant: After t iterations, there are exactly t elements in output (c) (3 points) Using the fact that output will have exactly k+ℓ elements and the loop invariant above, give a justification of why the algorithm is correct. (d) (3 points) Using the fact that output will have exactly k+ℓ elements and the loop invariant above, give a brief justification of why the runtime of this algorithm is O(k+ℓ)
The question is about Merge subroutine used in the MergeSort algorithm. Merge takes two sorted lists as input and merges them into a single sorted listBy addressing each part of the question, you will provide a thorough explanition of the correctness and runtime analysis of the Merge algorithm used in mergesort.