We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I would like to know the recurrence relation for K way merge sort i.e. instead of dividing the list into 2 parts, we will divide it into k parts at each recursive step. Now I have already calculated it but I don't know whether it is correct or not. I used the idea explained here: http://courses.cs.washington.edu/courses/cse373/01au/final-prob7.txt
I get the following:
T(n) = kT(n/k) + (k-1)*(2n-1) / 2 where n = mk and m is the size of partition. There are k partitions at each step. I would like to know if it right or not.
Best Answer
That doesn't seem quite right!
Assume we're at the stage where we have $k$ sorted array, each of size $m$ and we'd like to know how many comparisons are needed to form the final sorted array. Take the first two arrays, each of size $m,$ we need $2m-1$ comparisons to make a sorted array, then take the third and fourth arrays, again with $2m-1$ comparisons and continue to get to the final array. So far, we have done $k/2(2m-1)$ comparisons in total, as there're $k/2$ pairs, like $(1,2), (3,4), \cdots.$ Now, we have, $k/2$ arrays each of size $2m.$ With the same approach, take the first and second one (which the first is the result of the first and second arrays from the previous step), we need $4m-1$ comparisons. Again, continue pairing them up until you get the last array. In this step, we've done $(k/4)(4m-1)$ comparisons. Counting the comparisons of the previous step we have done $k/2(2m-1) + k/4(4m-1)$ comparisons in total, so far. Keep going until you get to the final step, where there is only one sorted array. Now, we have to sum up all comparisons. For simplicity, let $k=2^t,$ so $t=\log k$ Then the total number of comparisons is
$$k/2(2m-1) + k/4(4m-1)+\cdots + k/2^t(2^tm-1)$$
which is
$$\sum_{i=1}^t2^{t-i}(2^im-1)=t2^tm-(2^t-1) = n \log k - k +1$$
where we used $2^0+2^1+\cdots+2^{t-1} = 2^t-1$ and $mk=n.$
Therefore, $T(n)=kT(n/k) + n \log k - k + 1.$