GATE CSE 2005 | Question: 39

Question

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)

• A. $O(n \log \log n)$
• B. $\Theta(n \log n)$
• C. $\Omega(n \log n)$
• D. $\Omega\left(n^{3/2}\right)$

Comments

The k-way merge problem consists of merging k sorted arrays to produce a single sorted array with the same elements. Denote by n the total number of elements. n is equal to the size of the output array and the sum of the sizes of the k input arrays. For simplicity, we assume that none of the input arrays is empty. As a consequence , which simplifies the reported running times. The problem can be solved in running time with  space. Several algorithms that achieve this running time exist.

Using Heap: The idea is to maintain a min-heap of the k lists, each keyed by their smallest current element. A simple algorithm builds an output buffer with nodes from the heap. Start by building a min-heap of nodes, where each node consists of a head element of the list, and the rest (or tail) of the list. Because the lists are sorted initially, the head is the smallest element of each list; the heap property guarantees that the root contains the minimum element overall lists. Extract the root node from the heap, add the head element to the output buffer, create a new node out of the tail, and insert it into the heap. Repeat until there is only one node left in the heap, at which point just append that remaining list (head and tail) to the output buffer.

Source: https://en.wikipedia.org/wiki/K-way_merge_algorithm#Direct_k-way_merge

---

Adding @madhes23

Rather k-way merge that uses heap runs in O(nlogk), but direct k way merge is not optimized which runs in O(nk)

From wiki:

Direct k-way merge

In this case, we would simultaneously merge k-runs together.

A straightforward implementation would scan all k arrays to determine the minimum. This straightforward implementation results in a running time of Θ(kn). Note that this is mentioned only as a possibility, for the sake of discussion. Although it would work, it is not efficient.

We can improve upon this by computing the smallest element faster. By using either heaps, tournament trees, or splay trees, the smallest element can be determined in O(log k) time. The resulting running times are therefore in O(n log k).

Source – https://en.wikipedia.org/wiki/K-way_merge_algorithm#Direct_k-way_merge

---

@mohan123 what does the meaning of each level cost?

Answer 1

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$

Comments

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)

---

@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.

---

@MRINMOY_HALDER, According to your second approach time complexity is greater than when heap is used.

In approach 2,

You are not finding time complexity you are finding total number of elements..

2- way merge sort will merge 2 lists each from logn lists in level 1,

in level 2:: we have logn/2 lists with each list of size 2*(n/logn)...

in level 3:: we have (logn/$2^{2}$) lists with size 4*(n/logn)

.... so on till level k when there will be 1 single list..

in level k we have (logn/$2^{k}$) lists with size $2^{k}$*(n/logn)therefore,

logn/$2^{k}$=1 

logn= $2^{k}$ and k= loglogn..(Total Passes/Height of the tree)

Cost at each level/No of elements=n.

Hence T.C= cost at each level * height= O(n*loglogn).. 

So, according to me merge sort gives same result. Please tell me if I'm wrong.

 

 

Answer 2

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)

Comments

in question , number of elements in each lis is n/logn

so y = n/logn

---

0(xy*logx ) will satisfy because we can merge x arrays of each size y in0(xy*logx)..

Answer 3

Using Min Heap hope it can help...

Answer 4

This may help!!!