Assignment1-Part 1: 3-Way Merge Sort



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.


There are no reviews yet.

Be the first to review “Assignment1-Part 1: 3-Way Merge Sort”

Your email address will not be published.