Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 Coromano Jul 10 '13 at 12:09

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 Coromano Jul 11 '13 at 2:48

Your Answer


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.