edited by
6,625 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)$
edited by

5 Answers

Best answer
36 votes
36 votes

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
1 votes
1 votes

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/

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

7 votes
7 votes
1 answer
2
go_editor asked May 23, 2016
911 views
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two ...