You are handed k sorted lists and asked for one sorted list. What is wrong with concatenating and sorting?

Short answer

Merge k sorted lists with a min-heap that holds the current head of each non-empty list. Repeatedly pop the smallest value, append it, and push the next value from the same source list. This uses O(k) extra memory and O(N log k) time, preserving the sorted order already present in the inputs.

Concatenating is not incorrect, it is wasteful in a specific way

Say that first. The question is a trap for candidates who hear "what is wrong with" and assume the approach is broken. Concatenate all k lists and sort the result and you get the right answer every time.

The objection is that the input already carried the information the sort is about to compute. You were given k sequences in order. Sorting starts from the assumption that nothing is known about the order and reconstructs it from scratch, so you are paying to discover a fact you were handed.

That framing matters because it points at what a better algorithm must do: consume the existing order rather than rediscover it. A merge only ever compares the current front of each list, which is exactly the amount of comparing the given order leaves undone.

Two objections, and the second is the one that disqualifies it

The first objection is the bound. Let N be the total number of elements across all lists. Sorting the concatenation is O of N log N. A k-way merge is O of N log k, because each of the N elements is inserted into and removed from a structure holding at most k things.

Put a number on the gap so it is not just symbols. Ten lists of a million elements each gives N at ten million and k at ten. Log base two of ten million is about twenty-three; log base two of ten is about three and a third. So the merge does roughly a seventh of the comparison work, and the ratio widens as N grows against a fixed k.

The second objection ends the argument. Concatenation requires all N elements in memory simultaneously. The merge requires k, one per list, plus whatever the output consumes. If the k lists are files on disk, or partitions arriving over a network, or the sorted runs of an external sort, then concatenating is not a slower option, it is not an option. This is the industrial form of the problem: merging sorted runs is the final phase of external sorting and the mechanism behind compaction in a log-structured storage engine, and in both the whole point is that N does not fit.

An interviewer asking this question is usually checking whether you notice that. Candidates who answer only with the two complexities have answered the smaller half.

The merge

Seed a min-heap with the head of every non-empty list, tagged with which list it came from. Pop the smallest, append it to the output, and push the next element from that same list. The heap size never exceeds k.

// Each entry knows its source list, so the pop can pull that list's next element.
record Cursor(int value, Iterator<Integer> rest) {}

List<Integer> merge(List<List<Integer>> lists) {
    PriorityQueue<Cursor> heap =
            new PriorityQueue<>(Comparator.comparingInt(Cursor::value));

    for (List<Integer> list : lists) {
        Iterator<Integer> it = list.iterator();
        if (it.hasNext()) heap.offer(new Cursor(it.next(), it));   // empty lists never enter
    }

    List<Integer> out = new ArrayList<>();
    while (!heap.isEmpty()) {
        Cursor c = heap.poll();
        out.add(c.value());
        if (c.rest().hasNext()) heap.offer(new Cursor(c.rest().next(), c.rest()));
    }
    return out;
}

The seeding guard is not decoration. Pushing the head of an empty list means reading an element that is not there, and an implementation that handles the empty-list case only inside the main loop has already thrown by then. Empty lists, k equal to zero, and all lists empty are the three inputs that separate a submitted solution from a working one, and they cost one line between them.

The heap must be ordered by the value, and the entry must carry enough context to advance its own list. That coupling is the shape of the algorithm: the heap is not a collection of elements, it is a collection of positions.

What a merge preserves that a sort does not

Equal elements are where the two genuinely differ. The difference is in the output, not in the cost.

A merge that breaks ties by list order produces a deterministic and meaningful arrangement: among equal keys, everything from list one precedes everything from list two. That is often the requirement rather than a nicety. Merging time-ordered log files with second-granularity timestamps gives many ties, and keeping source order is what makes the merged log reproducible and diffable.

Sorting the concatenation gives you this only if the sort is stable and only if you concatenated in the intended order. Java's Arrays.sort on primitives is a dual-pivot quicksort and is not stable; on objects it is a merge sort variant and is. Relying on a property the chosen sort happens to have, without saying so, is the kind of thing that changes when someone swaps the sort.

If ties matter, make the comparator say so: compare on the key, then on the list index. Then the behaviour is in the code rather than in a library's implementation detail.

The same bound without a heap

Worth offering. It shows the bound is a property of the problem rather than of the priority queue.

Merge the lists in pairs. Round one merges list one with two, three with four, and so on, halving the number of lists. Each round touches every element once, so each round is O of N, and there are ceiling of log base two of k rounds. Total O of N log k, identical.

In practice it is frequently faster. A two-way merge is a tight loop over sequential memory with one comparison per output element and no pointer chasing, whereas a heap does a sift down of up to log k levels with two comparisons per level and jumps around an array of objects. It also parallelises without effort, because the pairs within a round are independent.

The cost is that it writes intermediate results, so it uses O of N extra space against the heap's O of k, and each element is copied log k times rather than once. Which of the two you want depends on whether memory or comparison count is the binding constraint, and saying that is better than declaring a winner.

The version external sorts use in practice is a tournament tree, sometimes called a loser tree: a complete binary tree over the k cursors where each internal node holds the loser of a comparison and the winner is propagated upward. Replacing the winner costs exactly one comparison per level, with no branch to decide which child to descend into, which is where its constant-factor advantage over a binary heap comes from. Same O of N log k.

When to write the simple one instead

The naive approach is to scan all k heads each time and take the smallest, which is O of N times k. For k in the low tens that is a handful of comparisons per output element with no allocation, no comparator, and nothing to get wrong, and it will beat the heap on small inputs.

Being able to say "at k around ten I would write the linear scan, and I would reach for the heap when k is in the hundreds or when the lists are streams" is the answer that reads as experience. It also demonstrates you know that log k is a small number precisely when k is small, which is the condition under which the clever version stops being worth its constant factor.

The k in the bound is the whole point: a merge holds one position per list instead of one slot per element, which is why it is both faster than sorting the concatenation and possible when the concatenation would not fit.

---

© 2026 Preptima. Originally published at preptima.com.