I want to show that if I apply the Mergesort on a set $M$ with $n$ elements and divide $M$ in $2<b\le n$ parts instead of just $2$, that the I need $O(nlog_2 (b))$ time for the merging part.
So far I went and said I have $n = b^k$ elements. So I have k iterations of merging.
My first question, when I am merging, do I merge $b$ subsets together or just two?
So I went with $b$ subsets:
In the first merging part I have $b^k (b-1) $ comparisons.
In the next one I habe $b^{k-1} (b^2-1) $ comparisons.
So in general there are at most $\sum_{i=0}^k b^{k-i} (b^{i+1}-1) $ comparisons.
Now I set $k = log_b(n)$, but I cant get anywhere from there..
Is there another way to approach this Problem?
Regards,
Chiray
P.S.: I hope my English is good enough to understand this.
If you use a priority queue for the merging phase, you never need to have more than $b$ elements in the queue. The insertion cost is therefore $O(\log b)$ for common implementations of priority queues.
The observation that leads to the use of a priority queue is simple. After the recursive calls, we have $b$ sorted lists. If we can efficiently keep track of the order of the $b$ elements at the fronts of those lists, we get to merge quickly. A priority queue can be used to store $b$ elements, each tagged with the list it comes from. The smallest element is extracted from the queue. Its tag tells us from which list to get another element. This new element is inserted in the queue.