28

Here is the problem: I have only 1GB RAM in computer. I have a text file of 10 GB data.This file contains numbers. How will I sort them?

Adding some more details.

 -They are all integers like 10000, 16723998 etc.   
 -same integer values can be repeatedly appearing in the file.
4
  • 3
    How big are the numbers? Are they integers, or arbitrary-precision? What format are they in? This is an interesting puzzle, but it's missing some details.
    – Joey Adams
    Aug 7, 2011 at 19:33
  • 1
    It's still not clear what the file format is. Are the integers signed 32-bit and written out in base 10 separated by nulls (\u0000)? Unsigned 64-bit packed in 8 bytes each? Also, how much scratch space is available on disk? Aug 8, 2011 at 7:00
  • This does not seem to be a programming puzzle of any kind, as this is a standard problem (though I suppose it gets much less attention in this era of copious memories). Migrating to Stack Overflow. Aug 8, 2011 at 21:06
  • One word: Rely on virtual memory. Aug 10, 2011 at 21:43

6 Answers 6

19

split the file into parts (buffers) that you can sort in-place

then when all buffers are sorted take 2 (or more) at the time and merge them (like merge sort) until there's only 1 buffer remaining which will be the sorted file

10
  • Yes, mergesort is the way to go here. (On the starting block level you can use any algorithm, though.) Aug 13, 2011 at 23:34
  • I too had thought of mergesort initially, but wouldn't merging n/2 and n/2 lead to a sorted array of size n? And memory size is the constraint here. So if you sort 2 chunks of 1 GB buffers individually, the merge would consist of 2 GB - which cannot be accomodated in memory. Aug 18, 2011 at 6:14
  • 4
    @saurabh those buffers are files that you stream so the full buffer doesn't need to be loaded in memory Aug 18, 2011 at 6:55
  • @ratchet freak, do you mean, first read a part of the file into a buffer (1 GB) and sort the buffer, then write the sorted buffer back to the file?
    – Alcott
    Sep 13, 2011 at 10:01
  • I have to use external merge sorting that is, Move partially sorted data as small chunks of files and do merge sort over. What could be the order of this algorithm? Similar to merge sort? As file read and write is specific to a platform, can we ignore them when calculating order? Aug 28, 2013 at 2:36
19

Please see this link. This guy has explained it beautifully.

An example of disk-based application:
External mergesort algorithm (wikipedia) -> A merge sort divides the unsorted list into n sublists, each containing 1 element, and then repeatedly merges sublists to produce new sorted sublists until there is only 1 sublist remaining.
The external mergesort algorithm sorts chunks that each fit in RAM, then merges the sorted chunks together.

For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

  1. Read 100 MB of the data in main memory and sort by some conventional sorting method, like quicksort.
  2. Write the sorted data to disk.
  3. Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file.
  4. Read the first 10 MB of each sorted chunk (of 100 MB) into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
  5. Perform a 9-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the 9 input buffers empties, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available. This is the key step that makes external merge sort work externally -- because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.
3
  • 2
    Link is not working.
    – Ravi
    May 19, 2022 at 18:52
  • 1
    can just remove the code format... scrolling horizontally is a bit difficult to follow
    – aanhlle
    Jul 20, 2022 at 9:33
  • @Ravi/@aanhlle text is now formatted! Jan 2 at 19:37
4

We use merge sort first data divided then merged .

  1. Divide the data into 10 groups each of size 1gb.
  2. Sort each group and write them to disk.
  3. Load 10 items from each group into main memory.
  4. Output the smallest item from the main memory to disk. Load the next item from the group whose item was chosen.
  5. Loop step #4 until all items are not outputted.
2

For sorting 10 GB of data using only 1 GB of RAM:

  1. Read 1 GB of the data in main memory and sort by using quicksort.
  2. Write the sorted data to disk.
  3. Repeat steps 1 and 2 until all of the data is in sorted 1GB chunks (there are 10 GB / 1 GB = 10 chunks), which now need to be merged into one single output file.
  4. Read the first 90 MB of each sorted chunk (of 1 GB) into input buffers in main memory and allocate the remaining 100 MB for an output buffer. (For better performance, we can take the output buffer larger and the input buffers slightly smaller.)
  5. Perform a 10-way merge and store the result in the output buffer.
  6. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the 90 MB input buffers empty, fill it with the next 90 MB of its associated 1 GB sorted chunk until no more data from the chunk is available.

This is the external merge sort approach which works externally.

1
  • 1
    What, ignoring a factor of 10, does this answer add to the information hyperlinked in Vivek Garg's answer or the accepted one? It has become regrettably commonplace to ignore things like generating the least amount of runs feasible or leave a bit of inversions for each merge to clean up (if memory serves, Knuth addresses both).
    – greybeard
    Nov 30, 2019 at 7:18
0

Step 1: Split the file into 10 chunks of 1GB, sort them in memory and store into disk

Step 2: Use a min heap and store first element of each sorted chunk along with it's chunk number, poll the minimum and stream to a new disk location, insert the next number of the polled number's chunk and repeat Step 2 until all elements are parsed and heap becomes empty

0

To sort an array, you can first sort the first two thirds, then the last two thirds and finally the first two thirds. So on the first pass, the largest n/3 numbers are guaranteed to be in the last two thirds (either sorted by the first pass or already present) and after the second pass the smallest are in the first two thirds, with the final pass sorting the array entirely. Using recursion, you can repeat this pattern down until the 'two thirds' are small enough to fit in RAM.

1
  • Please try to add an assessment of time needed where only one tenth of the data fits into RAM.
    – greybeard
    Apr 18 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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