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

---

Answer 1