Sorting a File Too Big for Memory

Imagine someone hands you a few shuffled index cards and asks you to put them in alphabetical order. You spread them across a table, find where each card belongs, and you are done.

Now imagine they arrive with a moving truck full of cards.

Your sorting method still works, but your table does not. At some point, the problem is no longer how to sort. It is where to put everything while sorting it.

I wanted to see that problem in practice, so I ran a small experiment. I took a CSV file containing roughly 2.2 million U.S. baby-name records and sorted it two ways:

1. Keep every row in memory, then sort the whole collection.
2. Use an external merge sort, which sorts smaller batches and temporarily stores them on disk.

Both approaches produced the same sorted result. They got there with very different bills.

One quick clarification: by “memory-safe” here, I mean that the amount of memory used stays under a chosen ceiling. This is about avoiding an out-of-memory crash when a file gets huge, not about the separate topic of programming-language memory safety.

The fast way: use a bigger table

The in-memory approach is the natural one:

flowchart LR
    I["2.2 million shuffled rows"] --> M["Put every row in memory"]
    M --> S["Sort the entire pile"]
    S --> O["Write the sorted file"]

This is like spreading every card across one enormous table. Once all the cards are visible, sorting is relatively quick.

The catch is that the table must be large enough before you begin. Double the number of rows and the program needs roughly twice as much room to hold them. If the input grows beyond the available memory, the approach stops working altogether.

The small-table way: external merge sort

An external merge sort accepts that the whole pile will not fit on the table. Instead, it uses the same small patch of table over and over.

For this experiment, that patch held 100,000 rows at a time.

Step 1: make sorted batches

The program picks up 100,000 rows, sorts only those rows, and writes that sorted batch back to disk. That file is often called a run. Then it clears the table and repeats with the next 100,000 rows.

flowchart LR
    I["Large shuffled file"] --> C["Read 100,000 rows"]
    C --> S["Sort this batch in memory"]
    S --> R["Write one sorted run to disk"]
    R -. "repeat with the next batch" .-> C

After the first pass, the original giant shuffled pile has become a set of smaller, individually sorted piles. The complete file is not sorted yet: a name near the end of the input might still belong before a name from the first batch.

Step 2: merge the batches

Now picture each sorted run as its own neat stack of cards. Because every stack is already sorted, the program only needs to compare the card at the front of each stack.

It chooses the earliest card, writes that card to the final file, and reveals the next card from the same stack. Repeat until every stack is empty.

flowchart LR
    R1["Run 1<br/>Aaliyah · Abigail · Ada · …"] --> P{"Which front row<br/>comes first?"}
    R2["Run 2<br/>Aaron · Avery · Bella · …"] --> P
    R3["Run 3<br/>Amelia · Ava · Emma · …"] --> P
    RN["More sorted runs<br/>…"] --> P
    P --> O["Final sorted file"]
    O -. "take one row, then compare again" .-> P

The clever part is that the program never needs to bring all those runs back into memory. It keeps one small working batch while creating the runs, then only the current candidate from each run while merging them.

Disk becomes the extra table space.

What happened

I measured heap allocations for both approaches and timed each run. Here are the headline results:

Metric	In memory	External merge sort
Peak live heap	389 MB	9.7 MB
Blocks alive at the peak	6.64 million	300,000
Total bytes allocated over the run	842 MB	697 MB
Allocation events	11.1 million	33.8 million
Heap still live at the end	1,103 B / 4 blocks	1,103 B / 4 blocks
Wall time	53 seconds	154 seconds

The external merge sort used about 40 times less memory at its peak: 9.7 MB instead of 389 MB. That is the big win.

The shape of the memory use matters too. The in-memory version kept climbing as it read more rows, peaking after the full dataset was loaded and the sort was underway. The external version reached its peak early, when one 100,000-row batch filled up, and did not need more room as the file grew. Its memory ceiling was tied to the batch size, not the total input size.

That is why the second approach can sort a file larger than the computer’s memory. A ten-times-larger input would create roughly ten times as many disk runs, but it would not require a ten-times-larger table.

So why was it three times slower?

The external version took 154 seconds instead of 53 seconds. Saving memory was not free.

The in-memory version reads each row, sorts everything, and writes each row. The external version has extra chores:

• It reads and sorts each batch.
• It turns the batch back into text and writes a temporary run.
• It reads and parses every temporary run again.
• It turns every row into text again for the final output.

That means more trips to disk and more handling of each row. The allocation count shows the same story: the external sort made 33.8 million allocation requests, about three times the in-memory version’s 11.1 million. Interestingly, those requests were smaller, so the total number of bytes allocated over the whole run was lower. There were simply many more little transactions.

Both approaches ended with the same tiny 1,103 bytes in four live blocks, so neither retained the dataset after finishing.

The batch-size dial

The 100,000-row batch size is not a magic number. It is a dial:

• Larger batches use more memory but create fewer temporary files and usually finish faster.
• Smaller batches use less memory but create more temporary files and add more merging work.

Turn the dial too far in either direction and a different resource becomes the problem. A giant batch can exhaust memory. Thousands of tiny batches can overwhelm the operating system’s limit on open files during the merge.

The useful setting is not “as small as possible.” It is “comfortably below the memory limit, while still large enough to avoid unnecessary disk work.”

The lesson

If a file comfortably fits in memory and speed matters most, the simple in-memory sort wins. It finished this experiment in about one-third the time.

If the file might be larger than memory, or if predictable memory use matters more than raw speed, external merge sort changes the question. Instead of asking, “Will this input fit?” you choose how large the program’s table is allowed to be.

That is the textbook trade-off made visible: RAM buys speed; disk buys room. External merge sort is slower not because it is a worse sorting algorithm, but because it is solving the harder problem of finishing with a table that is much too small for the pile.

The complete experiment is in the memory-safe data sorting repository.