hardHeap / Priority QueuePure DSA~33 min
Merge K Shard Streams
A query fans out to k database shards, and each shard returns its rows already sorted by timestamp. The coordinator must stitch the k sorted streams into one globally sorted result without loading everything and re-sorting.
Problem
Given k arrays, each sorted in non-decreasing order, merge them into a single non-decreasing array.
Input
A list of k arrays; total element count N across all arrays, 0 ≤ N ≤ 10^5, values in [-10^9, 10^9].
Output
A single sorted array of length N.
Constraints
- Each input array is individually sorted ascending
- 0 ≤ k and 0 ≤ N ≤ 100,000
- Target O(N log k) time
Examples
Example 1
Input
streams = [[1,4,5],[1,3,4],[2,6]]
Output
[1, 1, 2, 3, 4, 4, 5, 6]
Repeatedly emit the smallest available head across the three streams.
Example 2
Input
streams = []
Output
[]
No streams to merge.