A linear probing sort and its analysis(Preliminary Draft)

Publisher Website
Google Scholar
Abstract
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+@@@@2)n &equil; 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.

This publication has 0 references indexed in Scilit: