Shell sort is a generalisation of insertion sort. It sorts all th elements in a list as if they were interleaved lists. Shell sort begins with a large value of 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

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