The analysis of linear probing sort by the use of a new mathematical transform

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 probes into a table is presented. 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.