# K-way Merge — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/k-way-merge

> Merge k sorted lists efficiently using a min-heap that always holds the next-smallest candidate from each list.

## Beyond two-way merge

Merging two sorted lists is `O(n)` with two pointers. For **k** sorted lists, a **min-heap** holding one candidate per list generalizes this: always pop the smallest, then push that list's next element.

## Merge k sorted lists

Seed the heap with the first element of each list (tagged with its list/index so we know where to fetch the next value from).

```python
import heapq

def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return result
```

Output:

```
merge_k_sorted([[1,4,5],[1,3,4],[2,6]])
# [1, 1, 2, 3, 4, 4, 5, 6]
```

## Complexity & uses

With `n` total elements across `k` lists, this runs in `O(n log k)` — the heap never holds more than `k` elements. Used for merging sorted log files, external sorting, and the 'smallest range covering k lists' family of problems.