The asymptotic behaviour of a distributive sorting method
December 1983
Article
volume 31, issue 4 pp 287-303.
This publication is part of collection
| Related Files |
|---|
View PDF Version
(The_asymptotic_behavior.pdf, 0.6MB) |
In the distributive sorting method of Dobosiewicz, both the interval between the minimum and the median of the numbers to be sorted and the interval between the median and the maximum are partitioned inton/2 subintervals of equal length; the procedure is then applied recursively on each subinterval containing more than three numbers. We refine and extend previous analyses of this method, e.g., by establishing its asymptotic linear behaviour under various probabilistic assumptions.
Keywords
Automatically Extracted Terms
- distribution
- method
- result
- proof
- van dam
- uniform distribution
- analysis
- number
- section
- rinnooy kan
- condition
- uniform
- theorem
- probability
- dobosiewicz
- rinnooy
- lemma
- frenk
- case analysis
- behaviour
