Problem Set 3

Question 1

In the lesson on Recurrence, we implemented merge sort where we divided the array into two parts at each recursion step. Imagine you are asked to implement merge sort by dividing the problem into three parts instead of two. You can assume for simplicity that the input size will always be a multiple of 3. Use a priority queue to merge sub-arrays in the combine step.

a- Provide implementation for the 3-way division merge sort.

b- Provide a generalized expression for the number of recursion levels.

c- Work out the time complexity for the 3-way merge sort.

d- Will implementing merge sort by dividing the problem into a greater number of subproblems improve execution time?