1. [50 points] 3-way-Merge Sort: Suppose that instead of dividing in half at each step of...

  

Transcribed Image Text:

1. [50 points] 3-way-Merge Sort: Suppose that instead of dividing in half at each step of Merge Sort, you divide into thirds (as equally-sized as possible), sort each third, and finally combine all of them using a three-way merge subroutine, which combines three sorted arrays into one sorted array. a) What is the worst-case number of comparisons 3-way merge makes if given as input three arrays, each of size M? b) Write a recurrence relation T(N) that expresses the worst-case number of comparisons used in 3-way mergesort given an array of N elements as input. (We can assume that T(1) = 1.) c) Solve the above recurrence relation. d) Consider the following merge approach. You are given three sorted array, each of size M. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays. What is the worst-case number of comparisons in the above merging process? 1. [50 points] 3-way-Merge Sort: Suppose that instead of dividing in half at each step of Merge Sort, you divide into thirds (as equally-sized as possible), sort each third, and finally combine all of them using a three-way merge subroutine, which combines three sorted arrays into one sorted array. a) What is the worst-case number of comparisons 3-way merge makes if given as input three arrays, each of size M? b) Write a recurrence relation T(N) that expresses the worst-case number of comparisons used in 3-way mergesort given an array of N elements as input. (We can assume that T(1) = 1.) c) Solve the above recurrence relation. d) Consider the following merge approach. You are given three sorted array, each of size M. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays. What is the worst-case number of comparisons in the above merging process?

Answer rating: 100% (QA)

a WorstCase Comparisons in a 3Way Merge When merging three arrays the worst case scenario is examini... View the full answer