Problem

In a Meta-style ranking pipeline, multiple already-sorted candidate lists may need to be combined into one globally sorted stream. Given k sorted integer lists, merge them into a single sorted list.

Implement a function that takes a list of sorted lists and returns one sorted list containing all values from the input lists.

Formal Specification

• Input: lists, where lists[i] is a sorted list of integers in non-decreasing order
• Output: A single list of integers in non-decreasing order containing every element from all input lists

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 head across the 3 lists produces the globally sorted order.

Example 2

• Input: lists = [[], [0], [2,2,2]]
• Output: [0,2,2,2]
• Explanation: Empty lists contribute nothing, and duplicates must be preserved.

Constraints

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

Aim for a solution better than flattening everything and sorting again when k is large.