External Sort

External Sort:

What algorithm you will you use to sort data as big as 2 GB? A 2 GB data tells you that you can't bring all the data into the memory. We can and do bring only part of the data into memory. 

Here is the algorithm for external sort:

Algorithm External Sort: 

Suppose we can being only X MB of data into the memory for once.

1. Divide the file into k chunks, such that X*K = 2GB. Bring each chunk into memory and sort it using a $O(n*logn)$ algorithm. Save the lines back into the file.
2. Now, bring the next chunk into memory and sort.
3. once we're done, merge them one by one.

This is called as external sorting. And Step 3 is known as N-way merge.