1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
21
  • $\begingroup$ 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 $\endgroup$
    – Chiray
    Commented Jan 8, 2017 at 17:04
  • $\begingroup$ 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)$. $\endgroup$
    – Fabio Somenzi
    Commented Jan 8, 2017 at 17:09
  • $\begingroup$ I compare the first elements of the subsets, and remove the lowest element. $\endgroup$
    – Chiray
    Commented Jan 8, 2017 at 17:16
  • $\begingroup$ I continue doing this til one subset is empty $\endgroup$
    – Chiray
    Commented Jan 8, 2017 at 17:19
  • $\begingroup$ Do you know that I mean? $\endgroup$
    – Chiray
    Commented Jan 8, 2017 at 17:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .