Internal Sorting by Radix Plus Sifting

Abstract

A method is proposed for internal sorting which has the property that the expected time required per record, to sort n records with random keys, is a bounded function of n . Moreover the storage required in addition to that for the records is only 2 n address fields. It appears that the method may be a good choice when the number of records to be sorted is of the order of 10,000 or more. The method consists of partially sorting the records by a radix sort and completing the sort by sifting. In the radix sort, a list type of structure is used to present the distribution of the records.