# Run Time Analysis of the Merging Part in Mergesort

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.
• I don't know what a priority queue is, but that is also not what I want to show. I want to show, that if you use the basic merging algorithm, that you need $O(nlog(b))$ time Commented Jan 8, 2017 at 17:04
• What exactly is the "basic merging algorithm" for you? There are certainly ways to merge that cost more than $O(n \log b)$. If you do $b$ comparisons for each element you insert in the final sorted sequence, then obviously the cost of merging is $O(nb)$. Commented Jan 8, 2017 at 17:09