A033622 Good sequence of increments for Shell sort (best on big values).

1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609, 587521, 1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 67084289, 150958081, 268386305, 603906049, 1073643521, 2415771649, 4294770689, 9663381505, 17179475969

Offset

0,2

Comments

One of the best sequences of gaps' lengths for Shell sort. Giving asymptotic O(N^(4/3)), therefore it is efficient in case of big N. On small values (approx. < 4000), it is better to use A108870 or A102549. - Roman Dovgopol, May 08 2011

References

J. Incerpi, R. Sedgewick, "Improved Upper Bounds for Shellsort", J. Computer and System Sciences 31, 2, 1985. - Roman Dovgopol, May 08 2011

D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, 2nd ed, section 5.2. 1.

R. Sedgewick, J. Algorithms 7 (1986), 159-173 Addison-Wesley. ISBN 0-201-06672-6. - Roman Dovgopol, May 08 2011

Links

Nathaniel Johnston, Table of n, a(n) for n = 0..1000

Frank Ellermann, Comparison of Shell sorts based on EIS sequences. [broken link]

Wikipedia, Shellsort

Index entries for sequences related to sorting

Index entries for linear recurrences with constant coefficients, signature (1, 6, -6, -8, 8).

Formula

a(n) = 9*2^n - 9*2^(n/2) + 1 if n is even;

a(n) = 8*2^n - 6*2^((n+1)/2) + 1 if n is odd.

G.f.: (8*x^4 + 2*x^3 - 8*x^2 - 4*x - 1)/((x-1)*(2*x+1)*(2*x-1)*(2*x^2-1)). - Maksym Voznyy (voznyy(AT)mail.ru), Aug 11 2009

a(0)=1, a(1)=5, a(2)=19, a(3)=41, a(4)=109, a(n)=a(n-1)+6*a(n-2)- 6*a(n-3)- 8*a(n-4)+8*a(n-5). - Harvey P. Dale, Mar 02 2015

Maple

A033622 := proc(n) return (9-(n mod 2))*2^n-(9-3*(n mod 2))*2^ceil(n/2)+1: end: seq(A033622(n), n=0..29); # Nathaniel Johnston, May 08 2011

Mathematica

Table[If[EvenQ[n], 9*2^n-9*2^(n/2)+1, 8*2^n-6*2^((n+1)/2)+1], {n, 0, 30}] (* or *) LinearRecurrence[{1, 6, -6, -8, 8}, {1, 5, 19, 41, 109}, 30] (* Harvey P. Dale, Mar 02 2015 *)

Prog

(C) int sedg(int i){ return (i%2) ? (9*(2<<i)-9*(2<<(i/2))+1) : (8*(2<<i)-6*(2<<((i+1)/2))+1); } /* Roman Dovgopol, May 08 2011 */

Crossrefs

Sequences used for Shell sort: A003462, A033622, A036562, A036564, A036569, A055875, A102549, A108870.

Sequence in context: A100572 A119534 A306190 * A091568 A147307 A234801

Adjacent sequences: A033619 A033620 A033621 * A033623 A033624 A033625

Keyword

nonn,easy

Author

Jud McCranie

Status

approved