SHELLSORT WITH 3 INCREMENTS

Authors
JANSON S KNUTH DE
Citation
S. Janson et De. Knuth, SHELLSORT WITH 3 INCREMENTS, Random structures & algorithms, 10(1-2), 1997, pp. 125-142
Citations number
11
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
10
Issue
1-2
Year of publication
1997
Pages
125 - 142
Database
ISI
SICI code
1042-9832(1997)10:1-2<125:SW3I>2.0.ZU;2-D
Abstract
A perturbation technique can be used to simplify and sharpen A. C. Yao 's theorems about the behavior of shellsort with increments (h,g,1). I n particular, when h = Theta(n(7/15)) and g = Theta(h(1/5)), the runni ng time is O(n(23/15)). The proof involves interesting properties of t he inversions in random permutations that have been h-sorted and g-sor ted. (C) 1997 John Wiley & Sons, Inc.