An Adaptive Method for Unknown Distributions in Distributive Partitioned Sorting
- 1 April 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (4) , 367-372
- https://doi.org/10.1109/TC.1985.5009388
Abstract
Distributive Partitioned Sort (DPS) is a fast internal sorting algorithm which rung in O(n) expected time on uniformly distributed data. Unfortunately, the method is biased toward such inputs, and its performance worsens as the data become increasingly nonuniform, such as with highly skewed distributions. An adaptation of DPS, which estimates the cumulative distribution function of the input data from a randomly selected sample, was developed and tested. The method runs only 2-4 percent slower than DPS in the uniform case, but outperforms DPS by 12-13 percent on exponentially distributed data for sufficiently large files.Keywords
This publication has 9 references indexed in Scilit:
- The Design and Analysis of BucketSort for Bubble Memory Secondary StorageIEEE Transactions on Computers, 1985
- The design and analysis of a new hybrid sorting algorithmInformation Processing Letters, 1980
- The practical significance of D.P. sort revisitedInformation Processing Letters, 1979
- Implementing Quicksort programsCommunications of the ACM, 1978
- Sorting by distributive partitioningInformation Processing Letters, 1978
- Finding the medianJournal of Computer and System Sciences, 1976
- Expected time bounds for selectionCommunications of the ACM, 1975
- Time bounds for selectionJournal of Computer and System Sciences, 1973
- QuicksortThe Computer Journal, 1962