External Sorting - External Merge Sort

External Merge Sort

One example of external sorting is the external merge sort algorithm, which 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 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 (= 100MB / (9 chunks + 1)) of each sorted chunk 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. If the output buffer is full, write it to the final sorted file, and empty it. If any of the 9 input buffers gets empty, 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.

Read more about this topic:  External Sorting

Famous quotes containing the words external, merge and/or sort:

    “For those parents from lower-class and minority communities ... [who] have had minimal experience in negotiating dominant, external institutions or have had negative and hostile contact with social service agencies, their initial approaches to the school are often overwhelming and difficult. Not only does the school feel like an alien environment with incomprehensible norms and structures, but the families often do not feel entitled to make demands or force disagreements.”
    —Sara Lawrence Lightfoot (20th century)

    “Popular art is normally decried as vulgar by the cultivated people of its time; then it loses favor with its original audience as a new generation grows up; then it begins to merge into the softer lighting of “quaint,” and cultivated people become interested in it, and finally it begins to take on the archaic dignity of the primitive.”
    —Northrop Frye (b. 1912)

    “Is suffering so very serious? I have come to doubt it. It may be quite childish, a sort of undignified pastime—I’m referring to the kind of suffering a man inflicts on a woman or a woman on a man. It’s extremely painful. I agree that it’s hardly bearable. But I very much fear that this sort of pain deserves no consideration at all. It’s no more worthy of respect than old age or illness.”
    —Colette [Sidonie Gabrielle Colette] (1873–1954)