Stochastic Analysis of Shell Sort

Stochastic Analysis of Shell Sort

0.00 Avg rating0 Votes
Article ID: iaor20121064
Volume: 31
Issue: 3
Start Page Number: 442
End Page Number: 457
Publication Date: Nov 2001
Journal: Algorithmica
Authors: ,
Keywords: Brownian motion, sorting
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.