Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

It's known 2-way Merge sort takes N*logN time.

I wonder, what would be the running time if we split an array of the size N into N subarrays and then do the same thing as we would do for 2-way Merge?

share|improve this question
    
selecting the smallest of k (unsorted) elements takes O(k), if you split into 3 arrays you need 2 compares each step in the merge –  ratchet freak Jul 10 '13 at 12:01
    
@ratchetfreak, please have a look at my update. –  Alan Dert Jul 10 '13 at 12:09

1 Answer 1

Well, the recurrence will be:

enter image description here

where f(n) is the merge function.

Of course in 2-way merge sort we can do this in linear time, hence f(n)=O(n) for the k=2 case. But in general, the best time this can be done is O(nlogk), using Priority Queues.

Now, according to the Master Theorem you can solve this recurrence and see that T(n)=O(n log n).

So in asymptotic notation it looks like both k-way and the original merge-sort are equal. however note that in practice, implementing the original merge-sort is simpler and might require less effort to implement and maintain.

share|improve this answer
    
what's this formula, is this from Master method? –  Alan Dert Jul 11 '13 at 2:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.