## 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.

### MSC:

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