File ExternalSort.h

↰ Parent directory (ADS/sort)

The sort of a file larger than the memory, beyond the book, as Knuth describes it for tapes, here on sequences in memory that play the files:

Definition (ADS/sort/ExternalSort.h)

Detailed Description

  • replacementSelection() (5.4.1) makes the initial runs with a heap of M items: the least item of the current run goes out and the next input item takes its place, in the current run if it is not smaller than the one just written, in the next run otherwise; on random input the runs are about 2 M long, twice the M of sorting each memoryful, and a sorted input gives a single run;

  • polyphaseMerge() (Algorithm 5.4.2D) merges the runs on T tapes, T - 1 of input and one of output: the runs are dealt so that the counts on the tapes are a perfect Fibonacci distribution of order T - 1, padded with empty (dummy) runs, and each phase merges runs from all the input tapes onto the output one until one input tape is empty, which becomes the next output; each item takes part in about :math:` log_phi r ` merges for r runs with three tapes, fewer with more tapes, and no tape is ever only copied;

  • externalSort() is the two together.

The contracts [see File Contract.h]: M >= 1 and T >= 3; the runs are sorted and hold the items of the input, and the merge gives the items of the runs sorted, two audits. The functions are defined in ExternalSort.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, sections 5.4.1 and 5.4.2

    1. Gilstad, Polyphase merge sorting: an advanced technique, Proceedings of the Eastern Joint Computer Conference 18, 143-148, 1960

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions