Introduction to K-way Merge Pattern

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

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

You could put everything into one array and sort it. That costs O(N log N), and it throws away the fact that each list was already in order.

You could merge two lists, then merge the result with the third, and so on. That is better, but the growing result gets re-read on every merge.

Look at the smallest value in the final answer. It has to be the front of one of the lists, because each list is sorted