Suppose there are ⌈log n⌉ sorted lists of ⌊n / log n⌋ elements each. The time…

Concept. A min-heap holding k items answers insert and extract-min in O(log k) time, because either operation only walks the height of the heap, which is ⌊log2 k⌋. So k already-sorted lists holding N elements in total can be merged by keeping the current front element of every list in one min-heap of size k: each output element then costs one extract-min plus at most one insert, and the whole merge runs in Θ(N log k).

Application to this question.

1. Number of lists: k = ⌈log n⌉, so the min-heap holds at most about log n items — one front element per list.

2. Total number of elements: each list holds ⌊n / log n⌋ elements, so N = ⌈log n⌉ × ⌊n / log n⌋, which is of order n (exactly n when log n divides n evenly).

3. Cost of one heap operation: O(log k) = O(log(log n)) = O(log log n).

4. Total cost: each of the N elements leaves the heap exactly once and causes at most one insertion, so the merge costs (order n) × O(log log n) = O(n log log n).

Cross-check. Throwing the sortedness away and re-sorting all n elements from scratch with a comparison sort would cost Θ(n log n). The heap-merge replaces the per-element factor log n by log log n, and log log n grows strictly slower than log n, so the merge is asymptotically cheaper than re-sorting — which is exactly why the question points at a heap. A bound of order n·√n is polynomial in n and grows far faster still than any of the logarithmic-factor bounds.

Result. Producing the single sorted list takes O(n log log n) time.