Name
Abstract | ||
|---|---|---|
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. Key Words. Empirical distribution functions, Brownian bridge, Sorting algorithm, Random permutation |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/s00453-001-0048-0 | Algorithmica |
Keywords | Field | DocType |
Key words. Empirical distribution functions,Brownian bridge,Sorting algorithm,Random permutation model,Asymptotic distribution. | Stooge sort,Counting sort,Comparison sort,Discrete mathematics,Combinatorics,Pigeonhole sort,Insertion sort,Shellsort,Bubble sort,Sorting algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 3 | 0178-4617 |
Citations | PageRank | References |
2 | 0.45 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert T. Smythe | 1 | 92 | 39.96 |
| J. Wellner | 2 | 2 | 0.45 |