External merge sort algorithm

Question

I am having certain trouble understanding the merge step in external sort algorithm.I saw this example in Wikipedia but could not understand it.

One example of external sorting is the external merge sort algorithm, which sorts chunks that each fit in RAM, then merges the sorted chunks together. For example, for sorting 900 megabytes of data using only 100 megabytes of RAM: 1) Read 100 MB of the data in main memory and sort by some conventional method, like quicksort. 2) Write the sorted data to disk. 3) Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file. 4) Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.) 5) Perform a 9-way merge and store the result in the output buffer. If the output buffer is full, write it to the final sorted file, and empty it. If any of the 9 input buffers gets empty, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available.

I am not able to understand the 4th step here.Why are reading first 10MB of memory when we have 100 MB of available memory.How to we decide number of passes in external merge?Will we sort each chunk and store them in 9 files?

Answer 1

Suppose that you've broken apart the range to be sorted into k sorted blocks of elements. If you can perform a k-way merge of these sorted blocks and write the result back to disk, then you'll have sorted the input.

To do a k-way merge, you store k read pointers, one per file, and repeatedly look at all k elements, take the smallest, then write that element to the output stream and advance the corresponding read pointer.

Now, since you have all the data stored in files on disk, you can't actually store pointers to the elements that you haven't yet read because you can't fit everything into main memory.

So let's start with a simple way to simulate what the normal merge algorithm would do. Suppose that you store an array of k elements in memory. You read one element from each file into each array slot. Then, you repeat the following:

• Scan across the array slots and take the smallest.
• Write that element to the output stream.
• Replace that array element by reading the next value from the corresponding file.

This approach will work correctly, but it's going to be painfully slow. Remember that disk I/O operations take much, much longer than the corresponding operations in main memory. This merge algorithm ends up doing Θ(n) disk reads (I assume k is much less than n), since every time the next element is chosen, we need to do another read. This is going to be prohibitively expensive, so we need a better approach.

Let's consider a modification. Now, instead of storing an array of k elements, one per file, we store an array of k slots, each of which holds the first R elements from the corresponding file. To find the next element to output, we scan across the array and, for each array, look at the first element we haven't yet considered. We take that minimum value, write it to the output, then remove that element from the array. If this empties out one of the slots in the array, we replenish it by reading R more elements from the file.

This is more complicated, but it significantly cuts down on how many disk reads we need to do. Specifically, since the elements are read in blocks of size R, we only need to do Θ(n / R) disk reads.

We could take a similar approach for minimizing writes. Instead of writing every element to disk one at a time (requiring Θ(n) writes), we store a buffer of size W, accumulating elements into it as we go and only writing the buffer once it fills up. This requires Θ(n / W) disk writes.

Clearly, making R and W bigger will make this approach go a lot faster, but at the cost of more memory. Specifically, we need space for kR items to store k copies of the read buffers of size R, and we need space for W items to store the write buffer of size W. Therefore, we need to pick R and W so that kR + W items fit into main memory.

In the example given above, you have 100MB of main memory and 900MB to sort. If you split the array into 9 pieces, then you need to pick R and W so that (kR + W) · sizeof(record) ≤ 100MB. If every item is one byte, then picking R = 10MB and W = 10MB ensures that everything fits. This is also probably a pretty good distribution, since it keeps the number of reads and writes low.