Problem Set 3

Question 1

In the lesson on Merge Sort, 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 combining 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?

Question 2

We implemented unoptimized code for generating permutations of a string. The solution used extra space and also ran the main loop for the entire length of the array on each invocation. Given the following optimized solution, can you work out the time complexity?