3
$\begingroup$

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:

link

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

How do you load that entire list into memory? You don't. You have a bit of a misunderstanding about how Merge works, in this setting.

It's tempting to think that Merge should work as follows: load both input lists into memory, in their entirety; merge them; then write the result back out to storage. But that wouldn't work -- we won't have enough memory to load the entire lists into memory.

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ omg!! You are correct, when we will merge two sorted list it will take $O(1)$ memory space only. $\endgroup$
    – python
    Nov 15, 2015 at 3:17
  • $\begingroup$ But then why do we say that merge sort take $O(n)$ space while sorting? $\endgroup$
    – python
    Nov 15, 2015 at 3:22
  • $\begingroup$ 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 $\endgroup$
    – python
    Nov 15, 2015 at 3:34
  • $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Nov 15, 2015 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.