A102549 Optimal (best known) sequence of increments for shell sort algorithm.

1, 4, 10, 23, 57, 132, 301, 701, 1750

Offset

0,2

Comments

Values were found empirically. Better than A033622, A036562, A036564, A036569, and A055875.

Links

Table of n, a(n) for n=0..8.

Marcin Ciura, Best Increments for the Average Case of Shellsort, in R. Freivalds, (ed.), Fundamentals of Computation Theory: 13th International Symposium, FCT 2001, Riga, Latvia, August 2001, Lecture Notes in Computer Science, vol. 2138, Springer, pp. 106-117.

Example

a(0) = 1 performs a single pass of Shellsort with a gap size of 1 (which is identical to the Insertion Sort algorithm).
a(1) = 4 performs a single pass of Shellsort with a gap size of 4 (exchanging elements 4 positions apart if they are out of order).

Crossrefs

Cf. A033622, A036562, A036564, A036569, A055875.

Sequence in context: A200759 A159347 A137531 * A277789 A389251 A274019

Adjacent sequences: A102546 A102547 A102548 * A102550 A102551 A102552

Keyword

hard,nonn

Author

Gunther Piez (gpiez(AT)web.de), Feb 24 2005

Extensions

a(8) = 1750 from Roman Dovgopol, May 08 2011

Status

approved