Shell sort

Shell sort is a generalisation of insertion sort. It sorts all $h$th elements in a list as if they were $h$ interleaved lists. Shell sort begins with a large value of $h$ which is then reduced in a sequence.

Gap sequences

These gap sequences are difficult to pick and to analyse. Each sequence that contains 1, does a full insertion sort and is guaranteed a correct sort. One such sequence is Marcin Ciura’s $1, 4, 10, 23, 57, 132, 301, 701$

Ciura, Marcin (2001). “Best Increments for the Average Case of Shellsort”. In Freiwalds, Rusins. Proceedings of the 13th International Symposium on Fundamentals of Computation Theory. London: Springer-Verlag. pp. 106–117. ISBN 3-540-42487-3.

For this example we use the sequence $1, 3, 5$