I was reading about
external merge sort from the wikipedia article link, according to it:
External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). External sorting typically uses a hybrid sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted subfiles are combined into a single larger file.
Suppose we have a RAM which can only hold
2 chunks of data and we have
6 chunks of data to sort. Please see the below diagram:
Since our memory can hold
2 chunks of data so the first
step 1 sounds plausible since we are sorting only pairs of numbers (5,6), (3,4) (1,2). In the
step 2 we merge the data and now our chunk size is
4. My question is how do you now load this
4 chunk of data into memory now? Since your memory cannot accept more than 2 chunks of data then how do you load and sort them? How did you sort while merging chunks of data here? I have visited several links, but not able to understand this concept.
You must be performing some kind of sorting while merging the data as well right?