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?