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

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

Offset: 0

Author

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

Keywords

• hard
• nonn

Comments

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

Examples

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

Links

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

Crossrefs

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

Extensions

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