Now, we'll look at Shellsort which is a bit elementary on the face of it but it's not at all elementary as you'll see. The idea of Shellsort is that Insertion Sort is inefficient because elements really move only one position at the time even when we're kind of know that they have a long way to go. The idea behind Shellsort is that we'll move entries several positions at a time and the way we're going to do it, it's called h-sorting the array. So, an h-sorted array is h different inter leaves sorted sub-sequences so in this case with h=4 if we start at L and look at every fourth element - M, P, T - then it's sorted. If we start in the second place at E and look at every fourth element, it's sorted. So this is 4 interleave sequences, that's a 4-sorted array. And what we're going to do is implement a sorting method that h-sort for decreasing sequences of values of h. This is one of the oldest sorting methods invented by Shell in 1959. So, in this case, it starts out with the input example shown and then the 13-sort - a few items are moved, 4-sort - a few more are moved, and then finally, a 1-sort. And the idea is that each of the sorts can be implemented with only a few exchanges given that the previous ones happened. So first thing is how do we get an array h-sorted? That's actually pretty easy. We just use Insertion Sort but instead of going one back every time we come with a new item, we go h back. So for example when we come to this A in the Insertion Sort, then it's, we look at the array before that and then there was M and E in the positions three back so we exchange the A with the larger one to its left, that's M and then the other larger one to its left, that's E and then put it into position. So the code is the same as insertion, as for Insertion Sort, except that when we go backwards through the array we skip by h instead of just by one. That's how we h-sort an array. And the idea is we're going to use Insertion Sort because of two reasons based on our understanding of how Insertion Sort works. While the first thing is if the increments are big then the size of the sub arrays that we're sorting are pretty small so any sorting method including Insertion Sort is going to work well. But the other thing is if the increments are small because we've done previous h-sorts for bigger values of h, the array is partially sorted and so Insertions Sort is going to be fast. You wouldn't work to use Shellsort as the basis for h-sorting because that always takes quadratic time no matter what order there is in the array. So let's look at example of Shellsort with increment 7, 3, and 1. So, we start with this sort example and then 7-sorting it - just involves doing insertion sort but just reaching back 7 each time. In this case, the 4 subfiles stretched out at seven each only have two elements in them. And then we 3-sort. Now, because it's 7-sorted and a 3-sort elements are either already in placed or on a go back a few strides. On this case, it's only the A that goes back two. And then we 1-sort and again because of the fact that it's been 7-sorted and 3-sorted, the arrays are almost in order when it comes time to do the 1-sort and most of the items only go back one or two positions. So we have to do a few extra passes to do the higher sorts but the each element moves only a little bit on each path and that's how Shellsort gains its efficiency. So actually once you 1-sort, that's Insertion Sort so you're going to always get a sorted result. The only difference is how efficient is that. Now the intuition behind Shellsort and actually the mathematical fact is that if you've got an array that's h-sorted and then you k-sort it for another value k different from h, it's still h-sorted. This is one of those mathematical facts that seems obvious but then if you try to prove that maybe it's a little more subtle than you think. So, if you think of all this is, is, is trivial and easy, go ahead and try to write down a proof that a g-sorted array remains g-sorted even after it's h-sorted. But most people will accept that and it's a fact and that's how Shellsort gains efficiency. Now there's another problem is what increment sequence should we use for Shellsort. One of the first things you might think of is let's try powers of two. Actually that one doesn't work at all, very well at all because it winds up not comparing elements in even positions with elements in the odd positions until the 1-sort which means performance can be bad. Shell's original idea is to try powers to two minus one and that works okay. Knuth when he wrote his books in the 60s proposed the increment sequence 3x + 1. We'll start with the 1, 4, 13, 40, 121, 364 like that and that's good because it's easy to compute. When we're using in Shellsort of course, we find the largest increment less than our file size and then do the sorts for decreasing values of that increment. But finding the best increment sequence is a research problem that has confounded people for quite a long time. Here's an increment sequence that I found after maybe a year's work and it works well but nobody knows if that's the best one. So here's the implementation in Java of Shellsort for Knuth's 3x + 1 increment sequence. We'll just go ahead and compute the increments that are less than n, n / 3 and then starting at that increment whatever it is and say, we started 364 then next time we need an increment, we'll just divide it by 3, 364 integer divide by 3, 364 integer / 3 it gets 121, 40 and so forth. So, this h = h / 3 gets us to the next increment. And then, the implementation is just Insertion Sort. We just go through starting at h for i and when we do the insertion, the j loop, we decrement j by h each time, otherwise the code is exactly like Insertion Sort. So, just adding this extra loop for h-sorting and this extra loop to compute the increments to Insertion Sort, we get a slightly more complicated piece of code but its much, much more efficient. Here's what it looks like for a bigger array. We start with the randomly ordered input and you can see that it gets more and more in order on each time that we h-sort for the decreasing values of h. Here's an animation. This animation does the whole h-sort for each subarray. It's a little better feeling for what's going on. And now to do the high ones pretty quickly and now it's doing the 1-sort and again it steps through the array pretty quickly. If it's partially sorted it doesn't make much difference - does the higher sorts a little bit faster. But that's simple to implement and very efficient sorting algorithm. Now, the analysis of Shellsort is still open. Now, there's a few things that we can say. For example we can say that the number of comparison and the worst case is O(N3/2) for the 3x + 1 increments. But actually in practice it's much less than that. The problem is nobody knows an accurate model for describing the number of compares taken by Shellsort for any interesting increment sequence. This seems to be with a small value, multiple of n times the number of increments used which is some multiple maybe of n log n but nobody is been able to find an accurate model that proves that for any interesting increment sequence for Shellsort. So, why we are interested in this algorithm? Well, it's a simple idea that leads to substantial performance gains. It's very useful in practice because it's pretty fast except for very huge arrays. It's going to beat even the classical sophisticated methods for medium sized arrays. And it doesn't take much code. It's often used in embedded systems or in hardware sort type systems because there's so little code involved to implement it. And it just leads to a lot of interesting questions. This gets to the intellectual challenge of developing algorithms. If you think what we've been studying so far is trivial, go ahead and find a better increment sequence. Try some technique to discover one and try to say something about the average-case performance of Shellsort. People have been trying to do that for 50 years without a whole lot of success. So, the lesson is that we can develop good algorithms or good implementations without much code but there are some out there that are still waiting discovery. It could be that there are some increment sequence out there that make Shellsort more efficient than any other method, any of the sorting method that we know for pratical file size, no one can deny that. That's Shellsort or first non-trivial sorting method.
