Sorting a 500 GB CSV with 16 GB of RAM (External Merge Sort)

0) Problem Restatement

Microsoft asked: sort a 500 GB CSV file by one column, on a machine with 16 GB of RAM. The data doesn't fit in memory, so a normal sort won't work. We need an external sort: sort pieces in memory, save them to disk, then merge them.

1) Phase 1: Create Sorted Runs

1. Read the file in chunks of ~12 GB (leave room for overhead and the OS).
2. Parse each row, sort the chunk in memory by the key column, and write it to disk as a run (a sorted file).
3. 500 GB / 12 GB ≈ 42 runs.

Tips:

• Parse CSV properly: fields can contain quoted commas and newlines, so use a real CSV parser, not split(",").
• Convert the key to the right type (number vs string vs date) so "10" sorts after "9" when numeric.
• For a stable sort (keep original order for equal keys), include the original row number as a tie-breaker.

2) Phase 2: K-Way Merge

• Open all 42 runs and read a buffer from each (e.g., 100 MB × 42 ≈ 4 GB).
• Put the first row of each run into a min-heap keyed by the sort column.
• Repeatedly pop the smallest row, write it to the output buffer, and push the next row from the same run. Refill a run's buffer when it empties.
• Write the output in big sequential blocks.

import heapq, csv

def merge_runs(run_paths, out_path, key_index, key_type=str):
    files = [open(p, newline='') for p in run_paths]
    readers = [csv.reader(f) for f in files]
    heap = []
    for i, r in enumerate(readers):
        row = next(r, None)
        if row: heapq.heappush(heap, (key_type(row[key_index]), i, row))
    with open(out_path, 'w', newline='') as out:
        w = csv.writer(out)
        while heap:
            _, i, row = heapq.heappop(heap)
            w.writerow(row)
            nxt = next(readers[i], None)
            if nxt: heapq.heappush(heap, (key_type(nxt[key_index]), i, nxt))
    for f in files: f.close()

The run index i in the tuple also acts as a tie-breaker, and it keeps the merge stable across runs.

flowchart LR
    IN[("500 GB CSV")] --> C1["Chunk 12 GB - sort in RAM"]
    IN --> C2["Chunk 12 GB - sort in RAM"]
    IN --> C3["... 42 chunks"]
    C1 --> R1[("Run 1")]
    C2 --> R2[("Run 2")]
    C3 --> RN[("Run 42")]
    R1 --> M["K-way merge - min-heap"]
    R2 --> M
    RN --> M
    M --> OUT[("Sorted 500 GB output")]

3) How Many Passes?

• With 42 runs and enough memory for 42 read buffers, one merge pass is enough.
• If there were thousands of runs (tiny RAM), merge in rounds (e.g., 100 runs at a time), with multiple passes. Total I/O ≈ (1 + number of merge passes) × 2 × 500 GB (read + write per pass).
• Bigger initial runs mean fewer merge passes. A trick called replacement selection produces runs about 2x the memory size on average.

4) Performance

• The job is usually I/O-bound: 500 GB read + written twice ≈ 2 TB of I/O. At 500 MB/s that's ~70 minutes. On spinning disks, keep I/O sequential with large buffers.
• Put runs and output on a different disk than the input if possible.
• Use compression for runs (fast codecs like LZ4) if the CPU is idle and disk is the bottleneck.
• Parse and sort chunks in parallel on multiple cores while another thread reads the next chunk.

5) Scaling to Many Machines

• Sample the key column to find split points (e.g., 99 cut-offs for 100 machines), then range-partition: each machine gets the rows in its key range, sorts them locally (externally if needed), and outputs its part. Concatenating the parts in order gives the full sorted file (as TeraSort does).
• Fault tolerance: runs are files, so a crashed step can restart from the completed runs.

6) Wrap-Up

Read the file in chunks that fit in memory, sort each by the key (parsing CSV correctly, typed keys, row-number tie-breakers) and write sorted runs. Then k-way merge the runs with a min-heap and large sequential buffers, which takes one pass for ~42 runs. Keep I/O sequential, overlap reading and sorting, and for more scale range-partition by sampled key split points across machines.