ISSN:
1432-0541
Keywords:
Shellsort
;
Sorting
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We consider the worst-case running time of Shellsort when only a constant number,c, of increments are allowed. Forc=3, we show that Shellsort can be implemented to run inO(N 5/3) time, which is optimal. Forc=4, we further improve the running time toO(N 11/7), and, forc=5, we obtain a bound ofO(N 23/15). We also show anO(N 1+1/k ) bound for generalc, wherek=[(1+√8c+1)/4]. Forc=6, this isO(N 3/2).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01944355
Permalink