Merge K sorted lists

Merge several already-sorted lists into one sorted result by always taking the smallest available head, using a min-heap of the current heads.

The idea

Instead of comparing all k list-heads pairwise every round, push the current head of every list onto a min-heap, keyed by value. The heap top is always the smallest head overall, so popping it is an O(log k) decision. After taking it, push the next element from whichever list it came from. The heap never holds more than k elements.

Code

public static List<int> MergeKLists(List<List<int>> lists) {
    var heap = new PriorityQueue<(int list, int idx), int>(); // min-heap by value
    for (int l = 0; l < lists.Count; l++)
        if (lists[l].Count > 0) heap.Enqueue((l, 0), lists[l][0]);
    var result = new List<int>();
    while (heap.Count > 0) {
        var (l, idx) = heap.Dequeue();
        result.Add(lists[l][idx]);
        if (idx + 1 < lists[l].Count) heap.Enqueue((l, idx + 1), lists[l][idx + 1]);
    }
    return result;
}

Tips

• Compare this to merging two lists at a time: a heap collapses k lists into one O(log k) decision instead of k - 1 sequential merges.
• Track which list each heap entry came from, not just its value — you need to know where to pull the next element from.

In the .NET library

This is exactly how external merge sort combines sorted runs from disk, and how a log-aggregation system merges many time-ordered streams into one.