Stochastic analysis of Shell Sort. (English) Zbl 1064.68034

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.


68P10 Searching and sorting
68W05 Nonnumerical algorithms
Full Text: DOI