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

Author

Jud McCranie

Keywords

• nonn
• easy

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).

Crossrefs

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

Programs

C

int sedg(int i){ return (i%2) ? (9*(2<Roman Dovgopol, May 08 2011 */

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 *)

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