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

0Problem RestatementProblem

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.

1Phase 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.

2Phase 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.

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
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")]

3Deep Dive — How many times do you read 500 GB?Deep dive

Both phases are I/O bound, so the design goal is to minimise the number of passes over the data. Each pass is 500 GB read plus 500 GB written.

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
  R["42 sorted runs"] --> P1["Pass 1: 42 -> 21"]
  P1 --> P2["Pass 2: 21 -> 11"]
  P2 --> P3["Passes 3, 4, 5, 6"]
  P3 --> TOT["6 merge passes"]
  TOT --> IO["About 7 x 2 x 500 GB = 7 TB of I/O"]

total I/O ≈ (1 + 1) × 2 × 500 GB = 2 TB

%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
  IN["500 GB input"] --> RS["Phase 1 - build sorted runs"]
  RS --> NORM["Load-sort-write: runs about the size of memory"]
  RS --> REPL["Replacement selection: runs about 2x memory on average"]
  REPL --> FEWER["Roughly half as many runs"]
  FEWER --> ONE["One merge pass, with large read buffers"]
  ONE --> OUT["Sorted output - 2 TB total I/O"]

4PerformanceScale

• 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.

5Scaling 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.

6Wrap-UpWrap-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.