Merge K Individually Sorted Integer Arrays Into One Sorted Array

You are given k arrays of integers, each sorted in non-decreasing order. Return a single array that contains every element of every input array, keeping duplicates, in non-decreasing order.

The interviewer asked for this merge to be built with two named techniques, the two-pointer method and divide and conquer. The console checks only the returned array.

Function Signature

def merge_sorted_arrays(arrays: list[list[int]]) -> list[int]:

Rules

• The output length equals the total number of elements across all input arrays, and each value appears as many times in the output as it does across all inputs together.
• Any array may be empty, and so may the list of arrays. If there are no elements at all, return [].

Constraints

• 0 <= len(arrays) <= 10^4
• 0 <= len(arrays[i]), and the total number of elements across all arrays is at most 10^5.
• -10^9 <= arrays[i][j] <= 10^9
• Each arrays[i] is sorted in non-decreasing order.

Examples

Example 1

Input: arrays = [[1, 4, 9], [2, 2, 7], [3]]
Output: [1, 2, 2, 3, 4, 7, 9]

Example 2

Input: arrays = [[], [-5, 0], [], [-5, 10]]
Output: [-5, -5, 0, 10]

Empty arrays contribute nothing, and the duplicate -5 is kept.

Example 3

Input: arrays = []
Output: []