Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into two parts like Merge sort, 4-way Merge sort splits the array into four parts. 4-way Merge divides the input array into fourths, calls itself for each fourth and then merges the four sorted fourths.

a) Give pseudocode for 4-way Merge sort.

b) State a recurrence for the number of comparisons executed by 4-way Merge sort and solve to determine the asymptotic running time