Problem

In a Meta-style feed aggregation service, multiple independently sorted streams must be combined into one globally sorted result. Given k sorted integer lists, merge them into a single sorted list.

Formal Specification

Implement a function that takes lists, where lists[i] is a sorted list of integers in non-decreasing order, and returns a single list containing all values from every input list in non-decreasing order.

• Input: lists: List[List[int]]
• Output: List[int]

Examples

Example 1

• Input: lists = [[1,4,5],[1,3,4],[2,6]]
• Output: [1,1,2,3,4,4,5,6]
• Explanation: Repeatedly taking the smallest current element across the 3 lists produces the fully sorted merged result.

Example 2

• Input: lists = [[], [0], [-2, 7, 9]]
• Output: [-2,0,7,9]
• Explanation: Empty lists contribute nothing; the remaining values are merged in sorted order.

Constraints

• 0 <= k <= 10^4
• 0 <= len(lists[i]) <= 10^4
• -10^9 <= lists[i][j] <= 10^9
• Each individual list is already sorted in non-decreasing order.
• The total number of elements across all lists is at most 10^5.

Aim for a solution better than flattening and re-sorting all values when k is much smaller than the total number of elements.