An empirical study of the gap sequences for Shell sort - Radavičius, Irmantas; Baranauskas, Mykolas (Lietuvos matematikos rinkinys, 2013)
We present an improved version of the Shell sort algorithm. Using the algorithm, we study various geometrical sequences and the performance of Shell sort. We demonstrate that neither number of assignments nor the number of comparisons is sufficient to properly evaluate Shell sort and pick the optimal gap sequence. We argue that one should count both operations, as well as measure actual running times.
Keywords: sorting algorithm; Shell sort; gap sequence