in Algorithms edited by
6,599 views
32 votes
32 votes

You have $n$ lists, each consisting of $m$ integers sorted in ascending order. Merging these lists into a single sorted list will take time:

  1. $O(nm \log  m)$
  2. $O(mn \log  n)$
  3. $O(m + n)$
  4. $O(mn)$
in Algorithms edited by
6.6k views

2 Comments

There are n sorted lists, so there will be $logn$ levels, at each level $mn$ work will be done, Add the costs at each level, Hence the answer will be $O(mnlogn)$
13
13

$Ans:O(nm\ logn)$


8
8

5 Answers

36 votes
36 votes
Best answer

Answer is (B)

Since, $n$ lists of each size $m$.

Since, each list is sorted in ascending order use directly merge procedure of merge sort algo.

Take two list and merge..so one pair will take $\mathbf{2m}$ time.

So, total pairs in first level will be $n/2$. So total cost for one level is $\mathbf{(n/2)*2m=nm}$.

In next level cost for one pair is $4m$ and no of pairs will be $n/4$.. so next level cost will be $nm$.

So, like this each level will have cost $nm$.

No of levels will be when we have one complete list..

$\mathbf{n/2^k =1}$..

$\mathbf{k=\log_2^ \ n}$.

So, total cost  will be $\mathbf{ \log n *(nm)}$

edited by
by

4 Comments

0
0

@Shaik Masthan

thank you sir 😊 ...it was bit confusing...

 

0
0
What if the original n lists are unsorted?
0
0
1 vote
1 vote

Answer is B.

Apart from merge sort, this can also be done easily using a min Heap.

Given k sorted arrays of size n each, they can be merged into one single sorted array in time O(nk log k)

https://www.geeksforgeeks.org/merge-k-sorted-arrays/

4 Comments

0
0
So, it should be like this -
creating heap by taking an element from each sorted list( O(n) )
for m*n elements,
extract
heapify
add a new element from sorted list to heap(includes heapify).
end for

Time complexity = O(n) +mn(logn + logn)

correct ??
0
0
I think you are right. Hence the complexity becomes O(mn * log n).
0
0
0 votes
0 votes
Ans- B. O(mn log n)
0 votes
0 votes
By normal intuition also we can answer this

we have n lists

we have to merge into a single list

Time : mn(log(mn))

but here n>>m so log(mn) is simply logn also mn matters

hence answer is mnlog(n)
Answer:

Related questions