Article ID: | iaor20121064 |
Volume: | 31 |
Issue: | 3 |
Start Page Number: | 442 |
End Page Number: | 457 |
Publication Date: | Nov 2001 |
Journal: | Algorithmica |
Authors: | Smythe R T, Wellner J |
Keywords: | Brownian motion, sorting |
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