Merge k sorted lists

You are given a list of sorted lists. Return one sorted list that holds all their values. Some lists may be empty, and there may be no lists at all.

merge_k([[1, 4, 7], [2, 5, 8], [0, 6]])  ->  [0, 1, 2, 4, 5, 6, 7, 8]
merge_k([[], [3], [1, 2]])               ->  [1, 2, 3]

The heapq module is switched off for this problem: write the heap yourself. A heap is a plain list with sift up and sift down (lessons 1 and 2); you can copy your class from HEAP-P1.

One test passes in numbers that count how often they are compared with <, <=, > or >=. They behave like ordinary numbers otherwise. This is how the tests tell an O(log n) heap step from an O(n) scan, which a timer cannot always do.

Limits

• Up to 60,000 values in up to 300 lists. Use O(n log k) comparisons for n values in k lists.