Lets start from bottom.We have logn lists each of sizes of n/logn.So we take pairs of 2 and merge.

Here merge operations for each pair = 2n/logn and no. of pairs in total = logn/2(∵There are logn sorted lists, so logn/2 pairs).

So , total cost in last level = 2n/logn * logn/2 = n

Now we have logn/2 lists in next higher levels and each of size 2n/logn.So merge for each pair requires 4n/logn operations and we have logn/4 pairs in this level , so cost = 4n/logn * logn/4 = n

Hence cost remains n in each level.This we will continue till no. of list = 1 which can be found as:

logn lists at last level,logn/2 at 2nd last level and so on.Hence we have :

logn/2^{k } = 1 ⇒ logn = 2^{k}

⇒ loglogn = k which is the number of levels

And as we have calculated earlier cost at each level = n

Although the above solution is asymptoticaly best O(nloglogn) there exists O(nlogn) solution as well:

Just like in merge sort set initial pointer to each of the logn lists.Now at every step compare the local minimum of all the lists and advance the pointer of the list with minimum value .At each step we will have to logn comparisions as total lists are logn and total number of steps will be equal to n.

Lets start from bottom.We have logn lists each of sizes of n/logn.So we take pairs of 2 and merge.

Here merge operations for each pair = 2n/logn and no. of pairs in total = logn/2(∵There are logn sorted lists, so logn/2 pairs).

So , total cost in last level = 2n/logn * logn/2 = n

Now we have logn/2 lists in next higher levels and each of size 2n/logn.So merge for each pair requires 4n/logn operations and we have logn/4 pairs in this level , so cost = 4n/logn * logn/4 = n

Hence cost remains n in each level.This we will continue till no. of list = 1 which can be found as:

logn lists at last level,logn/2 at 2nd last level and so on.Hence we have :

logn/2

^{k }= 1 ⇒ logn = 2^{k}⇒ loglogn = k which is the number of levels

And as we have calculated earlier cost at each level = n

So overall complexity = O(nloglogn)

^{ }Although the above solution is asymptoticaly best O(nloglogn) there exists O(nlogn) solution as well:

Just like in merge sort set initial pointer to each of the logn lists.Now at every step compare the local minimum of all the lists and advance the pointer of the list with minimum value .At each step we will have to logn comparisions as total lists are logn and total number of steps will be equal to n.