4

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).

Sam
  • 86,580
  • 20
  • 181
  • 179
Alex
  • 41
  • 2
  • 3
    Given k homework tasks, each of unknown difficulty (not necessarily differing), where the total difficulty of all k homework tasks is n, it is usually beneficial to do your homework yourself. – flight Mar 27 '11 at 00:46
  • 1
    In defense of the OP, the homework tag was added by a different user (possibly speculatively). – dsg Mar 27 '11 at 01:00
  • Ahh.. yes, good point... still, it _could_ be homework... – flight Mar 27 '11 at 02:39
  • 1
    Haha, true. But that could be said for any question. – dsg Mar 27 '11 at 02:42
  • 1
    A similar question has been asked recently: http://stackoverflow.com/questions/5436523/merging-sorted-arrays-without-using-a-sort-function-in-java - see also the answers there – Thomas Mueller Mar 27 '11 at 08:38
  • @Thomas Mueller, your linked question is a simpler case where `k=2`. The difference surfaces when you're taking a min over the next item in all of the input lists. In the other question, this amounts to taking a min over `2` elements, in this case it amounts to taking a min over `k`. – dsg Mar 27 '11 at 21:44
  • 1
    @dsg I know, that's why I wrote 'similar' :-) – Thomas Mueller Mar 28 '11 at 04:09

2 Answers2

10

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).

dsg
  • 12,924
  • 21
  • 67
  • 111
  • 1
    Great solution! But what about the heapify operation at every step? I think time complexity will be O(nk logk) – Hengameh Jun 03 '15 at 11:26
0

Maybe just that the invariant is that the heap contains the smallest elements from the arrays that haven't been emptied. When you try to pop an item off list i, if this list is empty, you go on popping elements off the heap.

stringofquarks
  • 27
  • 5