Smythe, R. T.; Wellner, J. Stochastic analysis of Shell Sort. (English) Zbl 1064.68034 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 PDF BibTeX XML Cite \textit{R. T. Smythe} and \textit{J. Wellner}, Algorithmica 31, No. 3, 442--457 (2001; Zbl 1064.68034) Full Text: DOI OpenURL