Merge K Sorted Lists

Problem

Merge k sorted lists into one sorted list.

Use a min-heap of (value, list index, element index) seeded with the first element of every non-empty list, popping the smallest and pushing the next element from the same list. Return an empty list when there are no elements.

Hint

The list and element indices in the heap tuple keep equal values ordered deterministically.

Test cases

case 1

in: [[[1,4,5],[1,3,4],[2,6]]]

expected: [1,1,2,3,4,4,5,6]

case 2

in: [[]]

expected: []

case 3

in: [[[]]]

expected: []

case 4

in: [[[1],[2],[3]]]

expected: [1,2,3]

case 5

in: [[[-3,-1],[0,2]]]

expected: [-3,-1,0,2]

Starter codePython

def merge_k_sorted(lists):
    # Your code here
    pass

5 test cases · run your code against them in the editor