External merge sorting beyond available RAM

External merge sort handles a file larger than available RAM by creating sorted runs that fit in memory, then merging those runs with small buffers. For an engineer processing an export or log archive, the main planning questions are how many runs fit in one merge, how many complete passes the data needs, and how much temporary disk space remains available.

Use an illustrative sizing exercise: a 64 GiB file, a 256 MiB memory budget, and 128 MiB of decoded fixed-size records per initial run. The remaining memory is reserved for input buffers, sorting overhead, and bookkeeping. This is a planning model, not a measured throughput result or a claim that 128 MiB of arbitrary Python objects fits inside 128 MiB of RAM.

Produce runs with a stated memory allowance

Read one bounded chunk, sort it in memory, and write it as a sorted run. Repeat until the input is exhausted. With the simplified fixed-size representation, 64 GiB is 65,536 MiB, so 128 MiB runs produce 512 initial runs.

The chunk limit must apply to the representation actually held in memory. Parsing a compact text row into strings, dictionaries, and integer objects can consume much more memory than its source bytes. A practical implementation measures or bounds that representation and also reserves space for the sorting algorithm’s temporary storage.

Each run needs the same key definition, encoding, and tie policy. If one run sorts timestamps as text while another uses numeric values, a correct merge cannot repair the inconsistency. Store the format and key version with the job metadata so recovery does not accidentally combine incompatible runs.

Choose a merge fan-in from buffers and file handles

A k-way merge keeps one next record from each input run in a min heap. Remove the smallest candidate, write it, then replace it with the next record from the same run. Buffered reads amortize the cost of fetching those individual records from storage.

With 32 input runs and a 4 MiB buffer for each, input buffers use 128 MiB. A 4 MiB output buffer brings that subtotal to 132 MiB, leaving room in the 256 MiB budget for heap entries, decoded records, runtime overhead, and the operating environment. The exact safe fan-in also depends on the file-descriptor limit and record size.

Python’s heapq.merge provides the ordered iterator part for already sorted inputs. This small function demonstrates the merge stage using one integer per line; it is not the fixed-size representation used in the sizing arithmetic.

from contextlib import ExitStack
from heapq import merge
from pathlib import Path


def merge_integer_runs(paths, destination):
    source_paths = [Path(path).resolve() for path in paths]
    target = Path(destination).resolve()
    if target in source_paths or (target.exists() and
            any(target.samefile(path) for path in source_paths)):
        raise ValueError('destination must differ from all input runs')
    with ExitStack() as stack:
        files = [stack.enter_context(path.open()) for path in source_paths]
        streams = [(int(line) for line in file) for file in files]
        output = stack.enter_context(target.open('w'))
        for value in merge(*streams):
            output.write(f'{value}\n')

The destination check also rejects existing hard-link aliases of an input. The context stack closes every open file if parsing or writing fails. The function assumes every input run is already sorted and that the caller limits the number of paths. A full job should write to a temporary output path and publish that output only after successful completion.

Count complete read-and-write passes

Merging 512 runs in groups of 32 produces 16 larger runs. A second merge combines those 16 into the final output. There are therefore two merge passes after initial run generation. Each full pass reads and writes approximately the entire 64 GiB dataset if the representation size stays constant.

View full-size image ↗

Run generation transfers about 128 GiB: 64 GiB read and 64 GiB written. Each of the two merge passes transfers another 128 GiB, for 384 GiB total in this simplified model. Compression, filesystem metadata, caching, and record-format changes can alter physical I/O, so this number is an algorithmic transfer estimate.

Increasing fan-in can remove a merge pass, but tiny per-run buffers can produce poor I/O behavior and excessive open files. The choice is not simply to maximize the number of runs. Measure the actual storage and parsing path after calculating a feasible memory allocation.

Keep temporary storage recoverable

The original input, current runs, and a partially written next generation may coexist. In the example, keeping all three full datasets can approach 192 GiB before cleanup, apart from metadata and filesystem overhead. Deleting input runs only after their replacement is durable reduces risk but needs enough disk space to finish each merge group.

A run manifest can record its path, record count, key version, and completion state. Mark a run complete only after closing and verifying it. If the process stops halfway through a merge, discard or resume the incomplete output according to the format rather than treating it as a valid sorted run.

Stability requires another explicit policy. Preserve source order for equal keys by attaching an original sequence number or by maintaining a consistent run-order tie rule throughout every merge generation. A heap that breaks ties using an incidental filename does not automatically preserve the input’s order.

Evaluate storage traffic alongside comparisons

A heap-based merge performs O(log k) heap work per output record, while its buffered storage transfers are mostly sequential. The merge-sort structure still applies, but the memory boundary changes which costs dominate. An algorithm with fewer comparisons may lose if it repeatedly reads scattered disk locations.

Database systems expose related limits. PostgreSQL’s work_mem controls memory available to certain query operations before temporary files are used, and its documentation warns that multiple operations and sessions can consume separate allowances. A per-sort budget is therefore not the same as a machine-wide memory limit.

Test a merge with empty runs, negative values, duplicates across run boundaries, and a deliberately malformed line. Compare the final record count and sorted order with a trusted in-memory result on a small dataset. Keep those correctness checks separate from the large-file experiment, where measured peak memory, bytes transferred, temporary disk usage, and elapsed time answer different operational questions.

Publish a completed merge without exposing a partial file

The small merge function opens its destination for writing before it has parsed every input record. If a later line is malformed, that destination may already contain a partial result. Keeping an earlier completed output requires a separate publication step: merge into a temporary file in the destination directory, then replace the destination only after the merge succeeds.

import os
from tempfile import NamedTemporaryFile


def publish_integer_merge(paths, destination):
    source_paths = [Path(path).resolve() for path in paths]
    target = Path(destination).resolve()
    if target in source_paths or (target.exists() and
            any(target.samefile(path) for path in source_paths)):
        raise ValueError('destination must differ from all input runs')
    with NamedTemporaryFile(
        dir=target.parent, prefix='.merge-', suffix='.tmp', delete=False,
    ) as temporary:
        temporary_path = Path(temporary.name)
    try:
        merge_integer_runs(source_paths, temporary_path)
        os.replace(temporary_path, target)
    finally:
        temporary_path.unlink(missing_ok=True)

The temporary file is closed before the merge helper opens it, which also avoids relying on reopening an already open named temporary file. Locating it in the destination directory keeps the replacement on the same filesystem. Python documents os.replace as an atomic rename when successful, and documents the named-file lifecycle in tempfile.

Here atomic means a reader opening the destination sees the old completed file or the new completed file, rather than the growing merge output. A reader that already opened the old file can retain access to that old file under the operating system’s handle semantics. Atomic visibility is not a complete crash-durability guarantee: this helper does not synchronize file contents or directory metadata to durable storage. A recovery design must add the appropriate synchronization and manifest protocol for its platform.

View full-size image ↗

A small failure test should start with two sorted runs and a destination containing a recognizable previous result. Put a malformed line late in one run so that the failure occurs after some valid records have been written to the temporary file. The call must raise, the destination must still contain the previous result, and the temporary file must be removed. Then fix the malformed line and verify that the same destination becomes the complete sorted merge.

The final cleanup runs whether merging, replacement or the publication attempt fails. After a successful replacement the temporary path no longer exists, so the missing-path allowance is intentional. Abrupt process termination can still leave an orphan temporary file because Python cleanup may never run; a full job needs a way to identify and remove stale incomplete runs on restart.

The wrapper assumes the input runs remain unchanged and sorted while it reads them. It also assumes the job controls its source and destination paths. The replacement is not a lock coordinating two writers: concurrent jobs targeting the same destination need separate coordination if overwriting the other job’s completed result is unacceptable.

For an exercise, add this publication step to a two-generation merge plan and simulate failure after each completed group. Record which old runs remain needed and which new runs are complete. Recovery should depend on those recorded states, not merely on a filename existing. That connects the small parsing-failure case to the temporary-space and generation rules of the larger external sort.