# How to understand the storing mechanism used in external merge sort

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?

Instead, Merge works without loading either input list into memory all at once. Take a look at the pseudocode for Merge, and you'll see that it only needs to have two list items in memory at a time: one list node from somewhere in the first list, and one from somewhere in the second node. Merge finds which one of those two items is smaller, outputs it, and then loads the next item from the input list it came from. You can see that Merge only needs $O(1)$ memory to merge two sorted lists, even if the sorted lists are stored in external storage -- it never needs to load the input lists into memory in their entirety.
• omg!! You are correct, when we will merge two sorted list it will take $O(1)$ memory space only. Nov 15, 2015 at 3:17
• But then why do we say that merge sort take $O(n)$ space while sorting? Nov 15, 2015 at 3:22
• Hey If you see the visualization of merge sort how it is using O(1) time ? Obviously, it is loading whole chunk of data again. link Nov 15, 2015 at 3:34
• @python, this isn't a discussion forum, so we discourage asking follow-up questions in the comments. Instead, please ask a new question (but make sure to follow our quality standards, including researching the topic, showing your research and your thoughts). Standard mergesort is often implemented as an in-memory sort, so it stores the entire array in memory, thus uses $\Theta(n)$ space. External mergesort is a different algorithm; it's implemented withotu storing the entire array in memory, and thus uses much less space. I never said anything uses $O(1)$ time -- read again.