An Introduction of Shell sort, and a match with Insertion Sort.
For an introduction of Insertion sort, see here.
Optimizing for n=10
For a list of size 10, the gaps can be any number 1,2,….,9, and the sequence must end with 1. So each of the gaps 2,3,…,9 can be included in the sequence, or not included. So there’s a total of 2^8=256 possible gap sequences. For each we checked the average number of comparisons for all possible 10!=3628800 permutations.
Here are the 3 best sequences:
9-6-1: 25.512 comparisons
4-1: 25.516 comparisons
6-1: 25.539 comparisons
We could have also checked which has the highest probability of performing less comparisons than insertion sort. Here are the top 3 in this respect:
4-1: prob=0.72
9-4-1: prob=0.704
6-1: prob=0.701
Analyzing Shell sort variants
Say we start with the same permutation as shown in the beginning of the video, and use the gap-sequence 3-2-1. That is, the robot will sort with gaps of 3, then with gaps of 2. Just before concluding with an ordinary insertion sort, the list looks like this:
As you can see, each element is at most one hop away from its correct position. This is provably the case after sorting with gaps of 3 and 2. Here’s why.
The "non-messing-up" theorem
After sorting with gaps of 3, the list is said to be 3-sorted: each sublist with a gap of 3 is sorted.
Then we sort with gaps of 2, and the list becomes 2-sorted. Intuitively, it seems like this step messed up the previous step, and the list is no longer 3-sorted. Surprisingly, it still is.
It can be proven, and the proof is not at all trivial, that if the list is already p-sorted, sorting with a different gap doesn’t mess up this property.
Frobenius number
Now consider the element at position 9 (the right-most):
It’s surely brighter than the element at position 7, because the list is 2-sorted.
It’s also must be brighter than the element at position 6, because the list is 3-sorted.
Also for the element at position 5, because 9 is brighter than 7, and 7 is brighter than 5 (thanks to 2-sortedness).
Also for the element at position 4: 9 is brighter than 7 (2-sortedness) and 7 is brighter than 4 (3-sortedness).
So any sum of 2-s and 3-s is a gap that separates two sorted elements. Any positive integer larger than 1 is a sum of 2-s or 3-s. So each element is sorted with respect to all other elements, except perhaps the ones right next to it.
A generalization of this is as follows. The Frobenius number of {p1,p2,…,pk} is the largest integer that is not some sum of these numbers. For example, the Frobenius number of {2,3} is 1, and the Frobenius number of {2,5} is 3, and the Frobenius number of {5,9,11} is 17.
Now say the list is p1-sorted, and p2-sorted, and … pk-sorted, and the Frobenius number of {p1,p2,…,pk} is x. So each element is at most x hops away from its correct position. For larger distances, we can present the distance as a sum of elements from {p1,p2,..,pk}, and therefore the list is sorted for such distances.
This property is used in deriving upper bounds for Shell sort complexity.
Why did Shell sort lag behind in the second match?
In the second match, the optimized variant of Shell sort wins with faster time and lower number of comparisons (24 vs 30). However, during the match it is clear Insertion sort performs the comparisons faster. Why is that?
For each comparison, the robot performs these steps:
1) Pick up an element with the left hand.
2) Pick up an element with the right hand.
3) Compare them.
4) Put back the element in left hand.
5) Put back the element in right hand.
However, both Insertion sort and Shell sort often reuse the element they hold in their left hand, and compare several other elements with it. This allows them to skip steps (1) and (4) above, and save some time.
So how many times do they pick up an element with their left hand?
For Insertion sort the answer is easy: 9 times. It performs 9 iterations where it picks up one element, and compares it with some others until it finds the place for it.
Shell sort ends with an ordinary Insertion sort. So that requires picking up 9 elements just for that. And there is one more for gap=9, and four more for gap=6, so that’s a total of 14. These extra 5 slow it down a bit.