Internal and Tape Sorting Using the Replacement-Selection Technique

A general technique for sequencing unsorted
records is presented.  The technique is shown to 
be applicable for the first stage of a generalized sort
program (the formation of initial strings) as 
well as for sorting records within a memory storage (an
internal sort).  It is shown that given N records 
in memory storage, records are sequenced using 1+log2
N tests per record, that initial string lengths 
will average 2N for random input records, and that reading,
writing and processing can be accomplished 
simultaneously if the computer permits such overlap.

CACM May, 1963

Goetz, M. A.

CA630502 JB March 14, 1978  11:36 AM

1919	4	865
852	4	865
864	4	865
865	4	865
2017	5	865
74	5	865
851	5	865
865	5	865
865	5	865
865	5	865
849	6	865
850	6	865
851	6	865
852	6	865
853	6	865
854	6	865
855	6	865
856	6	865
857	6	865
858	6	865
858	6	865
859	6	865
860	6	865
861	6	865
862	6	865
863	6	865
864	6	865
865	6	865
865	6	865
866	6	865