An adaptive method for unknown distributions in distributive partitioned sorting

Distributive Partitioned Sort (DPS) is a fast internal sorting algorithm which rung in 0(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 Y–4 percent slower than DPS in the uniform case, but outperforms DPS by 12–13 percent on exponentially distributed data for sufficiently large files. © 1985 IEEE