# 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?

×