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.
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>