Complexity of merging n sorted lists

Given log n sorted lists each of size n/logn.What is the total time required to merge them to one single list?

22 Sep 2016 12:42 pm

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 =  1                     ⇒ logn = 2k

⇒ loglogn = k which is the number of levels

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

So overall complexity = O(nloglogn)

Prayas Sahni
23 Sep 2016 12:48 am

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.