# 4-way merge sort

Consider the modification of a 4 way merge sort which instead of dividing an array into two subarrays, 4-way merge sort divides the array into four sub-arrays and sorts each individual array recursively.

In the 2-way merge sort we have an index for each of the two sorted sub-arrays and we compare the elements they are pointing to and in worst case we perform $2k-1$ comparison where $k$ is the length of each array. Similarly in a $4$-way merge sort each of size $k$ we have and index for each of the four arrays. It takes $3$ comparisons to determine the smallest of the four. In worst case we must do this until each list has one element left for a total of $12(k-1)$ comparison. Finally we perform $3+2+1$ comparisons to finish the remaining list, thus for a total of $12k-6$ comparisons.

Based on the above merge procedure which of the following represents the correct running time for a $4$ way merge sort?

Details and Assumptions

-Ignore constant terms.

Is it possible to come up with a better worst case running time? is it asymptotically better?

×