Given 10 files each having 1 million integer in sorted order, physical memory have size of 3 million. Please suggest methods to extract 1 million integer in sorted form efficiently.
Asked
Active
Viewed 107 times
-3
-
Welcome to Stackoverflow! Please post a [minimal, Complete, and Verifiable example](http://stackoverflow.com/help/mcve), so that we can help you. – jhoepken Mar 22 '16 at 12:40
-
This is just an interview question. – Anirudh Gupta Mar 22 '16 at 12:41
2 Answers
0
If you want to deep into details, there's nice book icon from Knuth Sorting and Searching. It's bestseller in this topic, and gives understanding on the algorithms, which are being used even today.
On StackOverflow, there was really nice discussion, on how does the MapReduce algorithm work.
Or this discussion from programmers.stackexchange.com on sorting algorithms with limited resources.
0
Use a 10 way merge. Space for 1 million integers is needed for the result, so the remaining space of 2 million integers is split up into 10 parts, so buffer size for each of the 10 input files is 200,000 integers.
rcgldr
- 27,407
- 3
- 36
- 61