Let's start with an ordinary insertion sort.
This is the darkest element. It should be placed at the first position but this
short-sighted robot is going to require four comparisons to move it all the way to the front.
But here's an idea. Let's start over. We'll choose a sub list with a gap of two. That is, we picked
every second element. We'll now run insertion sort over this sub-list only. Because of the gaps it
will now be quicker to move the darkest element to its correct position - only two comparisons.
Similarly, the brightest element will be more quickly moved
closer to its correct position since it is moved with strides of two.
We'll now sort the other sub-list. Here too
this will bring the elements closer to where they belong in the full list.
We'll complete the sort with an ordinary insertion sort.
Since the elements are close to their correct positions this step will be much quicker now.
We can extend this idea to larger gaps. Here's a sub list with a gap of
five. Sorting it will also quickly move elements large distances improving the order of the list.
There are four more such sub-lists.
It's now easier to continue sorting with smaller gaps. We'll choose the
gaps according to the following scheme: first the length of the list divided by two,
which is five, as we've just done. Then divided by four and rounded down which is two.
After that we'll conclude with a gap of one.
The shell sort idea didn't work out so well so far. Let's try to see why. When sorting with gaps
the robot moved long distances from side to side which wasted time. Next
we're going to provide it with jet engines so it can do that more quickly.
Of course insertion sort will get the same boost as well. To reduce the number of comparisons let's
revisit the gaps it uses. Previously we used this gap sequence. It was generated by taking
the length of the list and repeatedly dividing by 2. This was the original description of Shell sort
but afterwards other variants were explored. This one for example is generated by powers of two
minus one. It can be shown to have a better worst case upper bound,
but generally analyzing Shell sort variants is difficult and there are many open questions. See
in the description more information regarding how it's done. But we have a simpler problem. We know
this robot will compete in sorting 10 elements so we can optimize it especially for this task.
We can scan all possible gap sequences and select the one that performs best on average.