The Gateway to Computer Science Excellence

0 votes

We can merge arrays in O($nk\log k$) time using Min Heap. Following is detailed algorithm.

**1.** Create an output array of size n*k.
**2.** Create a min heap of size k and insert 1st element in all the arrays into a the heap
**3.** Repeat following steps n*k times.

**a)** Get minimum element from heap (minimum is always at root) and store it in output array.

**b)** Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

Time complexity of producing a sorted list of all these element=O($nk\log k$)

Here K= $\log n$

n=$n\log n$

Time complexity of producing a sorted list of all these element=

O($nk\log k$)=O$(n\log n\log n\log \log n)$

Hence,**none of these.**

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

50,647 questions

56,497 answers

195,489 comments

100,803 users