Introduction to K-way Merge Pattern

You are given several sorted lists. Merge them into one sorted list.

[2, 6, 8]
[3, 6, 7]    becomes    [1, 2, 3, 3, 4, 6, 6, 7, 8]
[1, 3, 4]

Putting every value into one array and sorting takes O(N log N) time.

This ignores useful information. Every input list is already sorted.

The smallest remaining value must be at the front of one of the lists. We only need to compare those front values.

Store one front value from each list in a min heap.

Remove the smallest value, add it to the result, and insert the next value from the same list.

The heap contains at most `K