When an ORDER BY (or GROUP BY that needs sorted input) touches more data than fits in memory, a database can't just call one big in-memory sort. Instead: split the data into chunks small enough to sort in memory ("runs"), write each sorted run out to disk, then merge all the runs together into one final sorted result.

The missing link: a run is a stream, not a list

A run in a real external sort lives in a file on disk -- you read it sequentially, once. You genuinely cannot ask it for its 500th element without having already read the first 499, and you cannot ask how many elements it has without reading the whole thing. k_way_merge here takes each run as an ITERATOR (next()-only) instead of a list, specifically so that constraint is real and enforced, not just implied by prose: an implementation that tries to index into a run (runs[i][j]) simply cannot -- there's nothing to index into. The only thing you can do with an iterator is ask it, one at a time, "what's next."

create_sorted_runs (given) handles the splitting/sorting phase and hands back plain lists (so tests can inspect them), but external_merge_sort converts each one to an iterator before calling k_way_merge -- that's the actual interface your merge has to work against.

Implement k_way_merge(run_iterators): merge multiple already-sorted iterators into one fully sorted list, using a min-heap (heapq) so at every step you only ever hold ONE not-yet-emitted value per run, and pull that run forward by exactly one element once you emit it.

Example

k_way_merge(iter(r) for r in [[1, 4, 7], [2, 3, 8]])  # -> [1, 2, 3, 4, 7, 8]

Constraints

• run_iterators may be a one-shot generator, not a list -- materialize it once (e.g. list(run_iterators)) if you need to index by run number; never assume it supports indexing or a second pass itself.
• Use heapq, pushing (value, run_index) tuples -- run_index breaks ties on equal values deterministically (two equal values would otherwise make heapq compare the next tuple element, which doesn't exist here, so the tie-break index is required for equal values to stay comparable).
• After popping a run's current value, pull that SAME run's iterator forward exactly once (next()) to get its new current value, if it has one -- a StopIteration here just means that run is exhausted, not an error.

Real-world grounding

• Postgres's external sort (tuplesort.c, spills to disk and merges runs exactly this way for large sorts): src/backend/utils/sort/tuplesort.c

Real external sorts tune the number of runs merged at once (not always all k simultaneously -- sometimes multiple merge passes) based on available memory and I/O characteristics, and use replacement selection to produce longer initial runs than a naive chunk-and-sort -- but the core heap-based k-way merge over streamed runs is exactly what you're implementing here.