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 2 k 1 2k-1 comparison where k k is the length of each array. Similarly in a 4 4 -way merge sort each of size k k we have and index for each of the four arrays. It takes 3 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 ) 12(k-1) comparison. Finally we perform 3 + 2 + 1 3+2+1 comparisons to finish the remaining list, thus for a total of 12 k 6 12k-6 comparisons.

Based on the above merge procedure which of the following represents the correct running time for a 4 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?

T ( n ) = log 2 n + n T(n)=\log_2 n + n T ( n ) = k log 2 n + n T(n)=k\log_2 n +n T ( n ) = 3 2 log 2 n + n T(n)=\frac{3}{2}\log_2 n +n T ( n ) = n 2 + n T(n)=n^{2}+n

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

0 solutions

No explanations have been posted yet. Check back later!

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...