Editing External sorting (section)

===Additional passes===
The previous example is a two-pass sort: first sort, then merge. The sort ends with a single ''k''-way merge, rather than a series of two-way merge passes as in a typical in-memory merge sort. This is because each merge pass reads and writes ''every value'' from and to disk, so reducing the number of passes more than compensates for the additional cost of a ''k''-way merge.

The limitation to single-pass merging is that as the number of chunks increases, memory will be divided into more buffers, so each buffer is smaller. Eventually, the reads become so small that more time is spent on [[disk seek]]s than data transfer.  A typical magnetic [[hard disk drive]] might have a 10&nbsp;ms access time and 100&nbsp;MB/s data transfer rate, so each seek takes as much time as transferring 1&nbsp;MB of data.

Thus, for sorting, say, 50&nbsp;GB in 100&nbsp;MB of RAM, using a single 500-way merge pass isn't efficient: we can only read 100&nbsp;MB / 501 ≈ 200&nbsp;KB from each chunk at once, so 5/6 of the disk's time is spent seeking.  Using two merge passes solves the problem.  Then the sorting process might look like this:

# Run the initial chunk-sorting pass as before to create 500×100&nbsp;MB sorted chunks.
# Run a first merge pass combining 25×100&nbsp;MB chunks at a time, resulting in 20×2.5&nbsp;GB sorted chunks.
# Run a second merge pass to merge the 20×2.5&nbsp;GB sorted chunks into a single 50&nbsp;GB sorted result

Although this requires an additional pass over the data, each read is now 4&nbsp;MB long, so only 1/5 of the disk's time is spent seeking.  The improvement in data transfer efficiency during the merge passes (16.6% to 80% is almost a 5&times; improvement) more than makes up for the doubled number of merge passes.

Variations include using an intermediate medium like [[solid-state disk]] for some stages; the fast temporary storage needn't be big enough to hold the whole dataset, just substantially larger than available main memory. Repeating the example above with 1 GB of temporary SSD storage, the first pass could merge 10×100&nbsp;MB sorted chunks read from that temporary space to write 50x1&nbsp;GB sorted chunks to HDD. The high bandwidth and random-read throughput of SSDs help speed the first pass, and the HDD reads for the second pass can then be 2&nbsp;MB, large enough that seeks will not take up most of the read time. SSDs can also be used as read buffers in a merge phase, allowing fewer larger reads (20MB reads in this example) from HDD storage. Given the lower cost of SSD capacity relative to RAM, SSDs can be an economical tool for sorting large inputs with very limited memory.

Like in-memory sorts, efficient external sorts require [[Big O notation|O]](''n'' log ''n'') time: exponentially growing datasets require linearly increasing numbers of passes that each take O(n) time.<ref>One way to see this is that given a fixed amount of memory (say, 1GB) and a minimum read size (say, 2MB), each merge pass can merge a certain number of runs (such as 500) into one, creating a divide-and-conquer situation similar to in-memory merge sort. The size of each main-memory sort and number of ways in each merge have a constant upper bound, so they don't contribute to the big-O.</ref> Under reasonable assumptions at least 500&nbsp;GB of data stored on a hard drive can be sorted using 1&nbsp;GB of main memory before a third pass becomes advantageous, and many times that much data can be sorted before a fourth pass becomes useful.<ref>For an example, assume 500&nbsp;GB of data to sort, 1&nbsp;GB of buffer memory, and a single disk with 200&nbsp;MB/s transfer rate and 20&nbsp;ms seek time.  A single 500-way merging phase will use buffers of 2&nbsp;MB each, and need to do 250&nbsp;K seeks while reading then writing 500&nbsp;GB. It will spend 5,000 seconds seeking and 5,000&nbsp;s transferring. Doing two merge passes as described above would nearly eliminate the seek time but add an additional 5,000&nbsp;s of data transfer time, so this is approximately the break-even point between a two-pass and three-pass sort.</ref>

Main memory size is important. Doubling memory dedicated to sorting halves the number of chunks ''and'' the number of reads per chunk, reducing the number of seeks required by about three-quarters. The ratio of RAM to disk storage on servers often makes it convenient to do huge sorts on a cluster of machines<ref>Chris Nyberg, Mehul Shah, [http://sortbenchmark.org/ Sort Benchmark Home Page] (links to examples of parallel sorts)</ref> rather than on one machine with multiple passes. Media with high random-read performance like [[solid-state drive]]s (SSDs) also increase the amount that can be sorted before additional passes improve performance.