Questions about Shell sorting

Question

I am a sophomore student who's taking data structure class, and today the class was about sorting algorithms. We learned selection sort, Bubble sort, insertion sort, Shell sort, Quick sort, and merge sort (class was in this order). And from what I remember, Shell sort was made and designed to be faster than normal insertion sort.

So the procedure is:

1. divide original list into several sublists using gap.
2. sort the sublist using insertion sort.
3. continuously decrease the gap, and repeat until gap reaches 1.

I hope I am not wrong till this level. If I am please let me know.

If I'm right so far, my question is:

If this algorithm called "Shell sort" is designed and believed to be faster than just normal insertion sort, then why not use Shell sort recursively in step 2? using Shell sort instead of insertion sort when sorting sublists can make this faster according to this logic.

Answer 1

You have made an interesting observation. The recursive Shellsort idea has been put to use, to some extent, in OEIS sequence A036569 (search for it in the Wikipedia article [1]):

1 3 7 3*7 3*16 7*16 3*7*16 3*7*41 3*16*41 7*16*41 3*7*16*41...

However, as the plot at the bottom of [1] shows, this IS85 sequence, having large GCD between its gaps, is inferior to other sequences with small GCD between their gaps.

Apparently, the more the steps of Shellsort interweave the sublists, the fewer comparisons it makes overall (this is a conjecture based on empirical results, not a theorem). For an extreme example, read about the behavior of Shell's original gap sequence in [1].