IIIT Hyderabad Interview 2017

Question

You have 1 billions elements, but memory which can hold only 1 million. How would you sort it using merge sort?

Source-:https://gateoverflow.in/blog/4532/iiit-hyderabad-interview-experience-2017

Comments

is external sorting the answer for this? i.e dividing the input into chunks and sorting them individually and the merging the sorted chunks using merge procedure in the input source.

---

Yes, we need to do the external sorting.

Answer 1

We first divide the file into runs such that the size of a run is small enough to fit into main memory. Then sort each run in main memory using merge sort sorting algorithm. Finally merge the resulting runs together into successively bigger runs, until the file is sorted.

Source: https://www.geeksforgeeks.org/external-sorting/