Solution Set 3

Solution 1

a-

We can implement merge sort by dividing the initial input array into 3 subproblems instead of 2. The only caution we need to exercise is to carefully pass the boundaries for the three parts in the subsequent recursive portions. Combining the three arrays is equivalent of solving the problem of merging n number of sorted arrays, using a priority queue. One way the algorithm can be implemented is shown below.