Multiple Array Merge Using Binary Heap

Question

Given k sorted arrays of integers, each containing an unknown positive number of elements (not necessarily the same number of elements in each array), where the total number of elements in all k arrays is n, give an algorithm for merging the k arrays into a single sorted array, containing all n elements. The algorithm's worst-case time complexity should be O(n∙log k).

Answer 1

Name the k-sorted lists 1, ..., k.

Let A be the name of the combined sorted array.

For each list, i, pop v off of i and push (i, v) into a min-heap. Now the heap will contain pairs of value and list id for the smallest entries in each of the lists.

While the heap is not empty, pop (i, v) from the heap and append v to A. Pop the next item off list i (if it's not empty) and put it in the heap.

There are n additions and removals from the heap. The heap contains at most k elements at every time step. Hence the runtime is O(n log k).