1

This is a problem 2-1.b from CLRS. I don't understand how to merge n/k arrays of size k each in n*lg(n/k). The best solution I can come up with is to fill each entry of a final array of size n by searching for the min element amongst min elements of each sublist. This leads to O(nk). What is the algorithm to do it in specified time?

1

1 Answer 1

1

I just did this question, and I think the answer is as follows: Sublists are still merged two at a time. 1) Consider how long it takes to merge each 'level'. 2) Consider how many merge operations there are (number of 'levels' below the first list you start with).

How long to merge each level? Each sublist has k elements, and there are therefore (n/k) sublists. The total number of elements is therefore k * (n/k) = n, and so the merge operation at each level is theta(n).

How many merge operations (levels) are there?

If there is 1 sorted sublist: 0
If there are 2 sorted sublists: 1
If there are 4 sorted sublists: 2
If there are 8 sorted sublists: 3
If there are 16 sorted sublists: 4

1 = 2^0
2 = 2^1
4 = 2^2
8 = 2^3
16 = 2^4

So we can make a general rule, in the same format as the specific ones listed above:

If there are 2^p sorted sublists: p

When we need ask the question "2 to the power 'what?' = m", then we need a logarithm.

So, if we ask "2 to the power 'what?' = 16?" the answer is log to base 2 of 16 = lg 16 = 4

So asking how many levels of merge operations are there is the same as asking "2 to the power 'what?' = m". We now know that the answer is log to base 2 of n = lg m.

So we now know there are lg m levels of merge operations, and each level of merge operations takes n time. The total time is therefore n * lg m = n lg m

Remember, m is the number elements we want to merge, in this case, the number of sorted sublists returned by the insertion-sort part of the algorithm. This is n/k. So, the Total time is n log (n/k).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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