merging sorted arrays [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicates:

Merging two sorted lists

Algorithm for N-way merge

Given k sorted arrays each of length n, construct a single merged and sorted array.focus on running time and space 开发者_如何学JAVAcomplexity.

Source : Amazon interview question.

Any thoughts? thanks

---

Make a heap from the first element in each array. Pop the head element from the heap, insert it into the result array, and then take the next element from the array the head of the heap came from, and insert that into the heap. Repeat until you consume all of the arrays.