Question:

I was going over the 2 way merge sort algorithm and was thinking if by reducing the merge passes can we get better gain in terms of time.

E.g in a 2 way merge we have the following recurrence:

T(n) = 2T(n/2) + O(n)

and this has a time complexity of N.log-base2(N)

if I divide the problem by 4 and merge 4 sub arrays I will get

T(n) = 4T(n/4) + O(n)

and this should have a time complexity of N.log-base4(N)

Since, the number of merge passes has reduced, should this be something to consider when implementing merge sort ?

e.g with an array of 64 elements the first approach will have 6 passes and using the second approach it will have 3 passes.

Edit:

Ok, so with 2T(n/2) we are doing N comparisons per pass and with 4T(n/4) we end up doing 3*N comparisons per pass ? What about the cost of moving elements to result arrary, does that remain same at each pass ?

Answer1:Note that the base-4 log of a number is exactly half the base-2 log of a number; thus, you're only introducing a constant-factor speedup. Except you're not, because you introduce a similar constant-factor SLOWDOWN in the cost of the actual merging (2-way merge needs 1 comparison per item, 4-way may need up to 3). So while there may be fewer passes, the passes are each more costly. So you've complicated the code a fair bit, and the benefits are in question.

Answer2:It sounds reasonable but is not, because in this case you have to do at least 5 comparions to sort each 4 elements. This way you have 5*N*log4(N) comparisons and this is greater than N*log2(N) by factor 5*log(2)/log(4)

Answer3:Height of decomposition tree is log<sub>4</sub>n, but running time is not n log<sub>4</sub>n.

In first step you have four list of size n/4, their merge takes n/4 + n/4 + n/2 comparison. but in normal case it takes n/2 comparison, so you half the height of tree but you multiply each merge with two, so total running time is not better than division to 2 part. (you can prove for other depths of tree that you should have at least two times comparison compare to tree with two branch).

<hr /><em>P.S:By running time I mean number of comparison.</em>