A Linear Probing Sort and its Analysis (Preliminary Draft)

We present a variant of the distribution sort approach which makes use of extra storage to sort a list of n elements in an average of about (2+√) n = 3.412... n probes into a table. An accurate analysis of this technique is made by introducing a transform from a Poisson approximation to the exact (finite) distribution. This analysis also leads to the solution of an interesting parking problem.

Authors

• Gaston H. Gonnet
• J. Ian Munro

Keywords

No keywords are indexed for this paper.