Internal Sorting by Radix Plus Sifting
- 1 July 1966
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 13 (3), 404-411
- https://doi.org/10.1145/321341.321349
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.Keywords
This publication has 1 reference indexed in Scilit:
- Sorting on Electronic Computer SystemsJournal of the ACM, 1956