CMI2013-A-05

Question

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

• A. $O(nm \log  m)$
• B. $O(mn \log  n)$
• C. $O(m + n)$
• D. $O(mn)$

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)$

---

$Ans:O(nm\ logn)$

---

---

This can be done with heap sort also. Consider the best answer here Algorithms: GATE CSE 2005 | Question: 39

Answer 1

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)}$

Comments

@Aks9639

yes

@MRINMOY_HALDER

How ?

---

@Shaik Masthan

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

 

---

What if the original n lists are unsorted?

Answer 2

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/

Comments

@MRINMOY_HALDER

Refer this PYQ: https://gateoverflow.in/784/gate2005-39

---

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 ??

---

I think you are right. Hence the complexity becomes O(mn * log n).

Answer 3

Answer 4

Ans- B. O(mn log n)

Answer 5

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)