codejump
HardPro challengePythonJavaScriptTypeScript

Sorting — Merge K Sorted Lists

AlgorithmsSortingMerge SortDivide and Conquer

solve(lists) — lists is an array of k arrays, each sorted ascending (some may be
empty). Return one sorted array holding every value. With N values in total the
target is O(N log k), not O(N · k) and not a final sort() of everything.

Two classic ways: a min-heap holding one candidate per list, or divide and conquer:
merge the lists two by two (reusing the merge step from Merge Sorted Array), halving the
number of lists each round.

Examples

solve([[1,4,5],[1,3,4],[2,6]])  → [1,1,2,3,4,4,5,6]
solve([[],[]])                  → []
solve([[1],[0]])                → [0,1]

Sample tests

Test #1Three lists
Input: [[[1,4,5],[1,3,4],[2,6]]]
Output: [1,1,2,3,4,4,5,6]
Test #2All lists empty
Input: [[[],[]]]
Output: []
Test #3Two single-value lists
Input: [[[1],[0]]]
Output: [0,1]