CS 401 Algorithms
Extra Activity for Assignment1-Part 1 (48 points)
3-Way Merge Sort
Merge sort involves recursively splitting the array into two subarrays (as equallysized as possible), sorting them recursively and then finally merging three sorted
arrays into one sorted array.
a. What is the number of comparisons 3-way merge makes in the worst case if
given as input three arrays, each of size M?
b. Write a recurrence relation T(N) that expresses the worst-case number of key
comparisons used in 3-way mergesort given an array of N elements as input.
c. Solve the recurrence relation and provide the complexity in Big-O notation.
Please show your work.