GATE CS 2005 Q39 — Searching, Sorting, Hashing

We are given $k = \lceil \log n \rceil$ sorted lists, where each list contains $m = \lfloor n / \log n \rfloor$ elements.

The total number of elements across all lists is:

To merge $k$ sorted lists into a single sorted list, we can use a min-heap of size $k$:

1. Build the Heap: Insert the first element of each of the $k$ lists into a min-heap.
   Time complexity: $O(k) = O(\log n)$.
2. Extract and Insert: Repeat the following steps $N$ times (once for each element in the final sorted list):
   • Extract the minimum element from the heap and append it to the output list.
   • Insert the next element from the same list that contained the extracted element.
   Since the heap size is always at most $k$, each extract-min and insert operation takes $O(\log k)$ time.
   Total time for $N$ elements: $O(N \log k)$.

Substituting $N = n$ and $k = \log n$ into the complexity expression:

Thus, the time complexity of producing the sorted list is $O(n \log \log n)$, which matches Option A.