Merge many sorted feeds into one

Heaps and priority queues Mid-level Python 3.13+ Kotlin 2.4+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

import heapq
feeds = [[1, 7], [2, 3, 9], [5]]
print(list(heapq.merge(*feeds)))

Options[1, 2, 3, 5, 7, 9][1, 7, 2, 3, 9, 5][[1, 2, 5], [3, 7], [9]]

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [1, 2, 3, 5, 7, 9]

Right: one sorted output from three sorted feeds.

The standard library's merge keeps only one front value per feed in its heap, so memory stays O(k).

Why not the others?

B [1, 7, 2, 3, 9, 5]. That is plain concatenation.
C [[1, 2, 5], [3, 7], [9]]. merge yields single values, not groups.

30-second answer

Keep a min-heap holding the current front value of each feed, tagged with which feed and position it came from. Pop the smallest, output it, and push the next value from the same feed. With N values across k feeds, each value is pushed and popped once: O(N log k) time, O(k) heap memory.

Practise saying it · 45 s. No recording, just a timer

Explain merging k sorted feeds.

Say your answer out loud, then check which of these points you covered:

Heap of fronts
Pop, output, push next
O(N log k)

Deep dive

This is the k-way merge template; it also merges sorted files too big for memory.

Tagging with the feed index breaks ties so heapq never compares anything else.

Python's heapq.merge(*feeds) does the same lazily.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

from heapq import heappop, heappush


def merge_feeds(feeds: list[list[int]]) -> list[int]:
    fronts: list[tuple[int, int, int]] = []  # value, feed, position
    for f, feed in enumerate(feeds):
        if feed:
            heappush(fronts, (feed[0], f, 0))
    out: list[int] = []
    while fronts:
        value, f, pos = heappop(fronts)
        out.append(value)
        if pos + 1 < len(feeds[f]):
            heappush(fronts, (feeds[f][pos + 1], f, pos + 1))
    return out

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1

Kotlin 2.4

import java.util.PriorityQueue

fun mergeFeeds(feeds: List<List<Int>>): List<Int> {
    // value, feed, position
    val fronts = PriorityQueue<Triple<Int, Int, Int>>(
        compareBy({ it.first }, { it.second }))
    feeds.forEachIndexed { f, feed ->
        if (feed.isNotEmpty()) fronts.add(Triple(feed[0], f, 0))
    }
    val out = mutableListOf<Int>()
    while (fronts.isNotEmpty()) {
        val (value, f, pos) = fronts.poll()
        out.add(value)
        if (pos + 1 < feeds[f].size) {
            fronts.add(Triple(feeds[f][pos + 1], f, pos + 1))
        }
    }
    return out
}

Common mistakes

Concatenating and sorting, which is O(N log N) and ignores that the feeds are sorted.
Pushing whole lists into the heap, which compares lists and costs more.

Senior take & follow-ups

Say the cost as O(N log k) and explain why k, not N, is inside the log.

Follow-up questions

Think of your answer first, then open the hint.

What if feeds are endless streams?
Show hint
Same heap; pull the next item from a feed only after its current one is output.
How do you merge two feeds?
Show hint
Two pointers are enough; the heap pays off from three or more.

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.