Stochastic analysis of Shell Sort. (English) Zbl 1064.68034

Smythe, R. T.; Wellner, J.

Algorithmica 31, No. 3, 442-457 (2001).

Summary: We analyze the Shell Sort algorithm under the usual random permutation model. Using empirical distribution functions, we recover Louchard’s result that the running time of the 1-stage of \((2, 1)\)-Shell Sort has a limiting distribution given by the area under the absolute Brownian bridge. The analysis extends to \((h, 1)\)-Shell Sort where we find a limiting distribution given by the sum of areas under correlated absolute Brownian bridges. A variation of \((h, 1)\)-Shell Sort which is slightly more efficient is presented and its asymptotic behavior analyzed.

MSC:

68P10	Searching and sorting
68W05	Nonnumerical algorithms

Keywords:

empirical distribution functions; random permutation model; Brownian bridges