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

The Gateway to Computer Science Excellence

+42 votes

Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure)

- $O(n \log \log n)$
- $\Theta(n \log n)$
- $\Omega(n \log n)$
- $\Omega\left(n^{3/2}\right)$

+11

Refer this for better understanding of question.

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

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

+1

How can u take " n -nlog(logn)/logn , here we can take as nlog(logn)/logn "???

and this should not be the logic...

Anyone verify this..

and this should not be the logic...

Anyone verify this..

0

Try to solve the following problem -

https://www.interviewbit.com/problems/merge-two-sorted-lists-ii/

https://www.interviewbit.com/problems/merge-two-sorted-lists-ii/

+79 votes

Best answer

Since we have $\log n$ lists we can make a min-heap of $\log n$ elements by taking the first element from each of the $\log n$ sorted lists. Now, we start deleting the min-element from the heap and put the next element from the sorted list from which that element was added to the heap. (This identity can be done by making a structure of two values, one for the number and one for identifying the origin sorted list of that number and storing this structure in the heap). In this way each delete and the corresponding insert will take $O(\log\log n)$ time as delete in heap of size $n$ is $O(\log n)$ and inserting an element on a heap of size $n$ is also $O(\log n)$. (here, heap size is $\log n$). Now, we have a total of $\log n \times \frac{n}{\log n} = n$ elements. So, total time will be $O(n \log\log n)$.

Correct Answer: $A$

Correct Answer: $A$

0

How the deletion in heap takes O(1) time? Can you please explain? I think it should be O(log n) (if no. of elements are n) in this case it will be O(log log n) although the answer will still remain same.

+1

Sorry Arjun Sir, but I am bit confused in it.

Yes, Saurabh is right that to preserve heap property, taking out min element will take O(logN) time ( so here it is loglogn ). But how this deletion is actually working here in this question??

1. We have created min-heap with O(log n) by considering the first element in each sorted list

2. In order to take out min element (deleting) will be down by swapping min with last element... So, here are we swapping the entire two nodes or just 2 elements???? It cannot be elements, because then sorted order cannot be maintained in each node AND how can it even be entire node swap? because after swap, in order to delete min element ( which is start of the list) we have to take it to the last through n/log(n) elements (or shift rest of the list to left by 1 position) and the go for preserving the heap property. So, answer will change in this case. (Kindly note that, if we ignore this fact on shifting.. Then I am getting the correct answer as nloglog(n) )

Can you clarify where am I going wrong??

+1

Sir if we have 2 sorted lists containing m and n elements then we can merge it using merge procedure from merge sort in O(m+n) so here if we have k sorted lists containing e elements then we can merge it in O(ke) which would be O(logn * (n/logn)) = O(n). So why not use this ?

0

Creation of heap is fine , but at the end sorted list is required ... dig little bit more approach is fine.....

0

@Saurabh & @Tushar ....

heapify takes O(log n) and deletion takes of any element O(n) , you guys are right !!! BUT there is a "but"...

HERE YOU ARE DELETING THE MINIMUM ELEMENT FROM THE MIN HEAP which takes O(1) :-)

heapify takes O(log n) and deletion takes of any element O(n) , you guys are right !!! BUT there is a "but"...

HERE YOU ARE DELETING THE MINIMUM ELEMENT FROM THE MIN HEAP which takes O(1) :-)

0

Though the answer is correct but I don't see build heap procedure in the answer(they have assumed it).

0

all the logn lists are already sorted in given question... So there is no need to consider them as min heap & apply deletion of logN time... You can select the next minimum element in O(1) time by looking at 2nd element of list who's first element (min element among all the n elements) is deleted...

0

0

why ???

In logn way merge, for single elements there is logn comparison.

so, total no. of comparison is logn*n/logn = n

0

Show your detailed work... How many levels it is going, on each level how much work it's carrying !

If you are right, then this answer must be wrong...

If you are right, then this answer must be wrong...

0

Shaik Masthan sir,

I'm confused with these following approach.

3-way merge means, all 3 lists will be merged into a single list in one level.

4-way merge means, all 4 lists will be merged into a single list in one level.

k-way merge means, all k lists will be merged into 1 list in one level.

like that, logn way merge means, all logn lists will be merged into a single list in one level.

**Approach - 1**

In case of 2-way merge we're doing like this - when 2 lists of size m & n are present & we merge them in O(m+n) time where m+n is the total no. of comparison.

like wise there are logn lists, each one having n/logn elements.

$\frac{n}{logn}$, $\frac{n}{logn}$, $\frac{n}{logn}$,........................logn times

so, T.C is $O(\frac{n}{logn}+\frac{n}{logn}+\frac{n}{logn}+.........logn)$

T.C is $O(\frac{n}{logn}*logn)$ = O(n)

**Approach-2**

see, there are total n elements in the output array,

for each of these n elements, we need atmost logn comparison(as we're using logn lists to compare)

hence, T.C = O(nlogn)

please help. I'm confused

0

Key point is :-

In 2 way merge sort, in one level you can merge two lists with O(m+n) comparison

In 3 way merge sort, also we can do that with O(m+n+p) comparisions ?

In 2 way merge sort, in one level you can merge two lists with O(m+n) comparison

In 3 way merge sort, also we can do that with O(m+n+p) comparisions ?

0

see direct k-way merge here - https://en.wikipedia.org/wiki/K-way_merge_algorithm

time complexity is given as O(nk), which means for 3-way mege we can do like this O(m+n+p)

0

@Shaik Masthan sir

As maximum comments are referring for 2-way merge sort even though question specifically mentioned for $heap.$ Here in this case both the approaches are giving same answer.

My question--if there is a change in the question in the # of sorted list and # of elements in each sorted list. Does both the approaches still gives the same answer. As making use of 2-way MS is easy compared to think in terms of heap. Please help me out.

+14 votes

We can merge x arrays of each size y in in O(xy*Logy) time using Min Heap.

x = n/Logn

y = Logn

We get O(n/Logn * Logn * Log Log n) which is O(nLogLogn)

+8 votes

Number of List = Log(n) , Number of elements in each list = n/Log(n)

Take the pair appraoch( like merge in pairs , (1,2) is first pair , (3,4) is the second pair , (4,5) , (6,7)...... (log(n) - 1,logn) will be the log(n)/2 th pair and merge using merge procedure of mergesort which takes Theta(k) where k is the number of elements in big one list.

Thus for first attempt the work will be [ ( n/log(n) ) * ( log(n)/2 ) ]= n/2 as theta(n/log(n)) work has to be done for each pair and total log(n)/2 pairs are there

Second attempt , as now we have ( log(n)/2 ) list so again make pairs but now element in each list is 2n/log(n)

thus work will be => ( 2n/logn) * (log(n)/4 ) = n/2

similliarly again number of list will be half then make pairs thus for third attempt work will

be = (4n/logn) * (log(n)/8) = n/2

and so on....

total log(logn) attempt will be there , after that we will get single list of n elements

Thus (n/2 + n/2 + n/2 + ....... log(logn) terms )

thus ans = (n/2)* ( log(logn) ) = n log(logn)

Take the pair appraoch( like merge in pairs , (1,2) is first pair , (3,4) is the second pair , (4,5) , (6,7)...... (log(n) - 1,logn) will be the log(n)/2 th pair and merge using merge procedure of mergesort which takes Theta(k) where k is the number of elements in big one list.

Thus for first attempt the work will be [ ( n/log(n) ) * ( log(n)/2 ) ]= n/2 as theta(n/log(n)) work has to be done for each pair and total log(n)/2 pairs are there

Second attempt , as now we have ( log(n)/2 ) list so again make pairs but now element in each list is 2n/log(n)

thus work will be => ( 2n/logn) * (log(n)/4 ) = n/2

similliarly again number of list will be half then make pairs thus for third attempt work will

be = (4n/logn) * (log(n)/8) = n/2

and so on....

total log(logn) attempt will be there , after that we will get single list of n elements

Thus (n/2 + n/2 + n/2 + ....... log(logn) terms )

thus ans = (n/2)* ( log(logn) ) = n log(logn)

+2 votes

Please correct me if I am wrong.

- See, if we use merge sort algorithm then it uses divide and conquer mechanism and divide the list into small parts and then merge them by using merge procedure.
- Now in any level, there is n/logn elements in the array and we need to merge them. To merge two array of size n/2 merge procedure take O(n/2+n/2) = O(n) time.
- So to merge two array of size n/logn it will take 2n/logn time.
- Now total number of such pair will be number of array/2 =logn/2
- so in each level total number of comparison/movement will be sum of comparison/movement of all the pairs.
- Total number of pairs = logn/2
- each pair take 2n/logn time to get merge.
- So total time taken at each level will be (2n/logn)*logn/2 =n.
- Now the depth of the tree formed by merge sort while dividing the problem into subproblem is equal to logm for m elements.
- So for logn elements the depth of tree will be loglogn.
- Now we merge each pair until it get merge till the root level of the tree so total loglogn level require and each level take time equals to n
- So total time taken will be O(nloglogn)

+1 vote

Lets start with 2 list each of size n

to merge them we will need, O( n+n ) = O (2n)

similarly to merge k list of size n = O ( kn )

Now to merge log(n) lists of size n/log(n)

it will take O ( log(n) * n / log(n) ) = O ( n )

to merge them we will need, O( n+n ) = O (2n)

similarly to merge k list of size n = O ( kn )

Now to merge log(n) lists of size n/log(n)

it will take O ( log(n) * n / log(n) ) = O ( n )

0

Merging 2 lists of size n will take O(n) , that's fine, but the question is on two - way merge (sorry i did not mention it before) so we have to merge lists multiple times rather than just merging lists once.

If merge was to be done only once it would be O(n).

This is my understanding of the question, please correct me if I am wrong.

If merge was to be done only once it would be O(n).

This is my understanding of the question, please correct me if I am wrong.

0

ya you are also making a good point here,

for first merge its = O ( 2n )

second = O ( 3n )

ans so on for (k-1)th merge = O ( kn )

---------------------------------------------

in total = O ( 2n + 3n + ......+ kn ) = O ( k^{2} n )

so in case of this question = O ( log^{2}(n) * n / log(n) ) = O ( n * log(n) )

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,394 answers

198,594 comments

105,446 users