Shell Sort

Let’s look back yet again and see if we can develop a mental picture of the three sorts we’ve covered so far: Simple Sort; Selection Sort and Insertion Sort.

Simple sort is creating a new deck of sorted cards by finding the lowest card in the unsorted pile. It consists of an inner loop and an outer loop where the inner loop is used to iterate through the unsorted portion of the deck and the outer loop ensures we consider the iterate through the inner loop once for each element in the array of cards. Simple sort zeroes a min value between the loops (which is to say between iterations of the unsorted deck) and updates the min value in the inner loop. With each iteration of the inner loop, we append to the newly growing array.

Simple sort is the ‘intuitive’ sort.

Selection sort differs from Simple sort in that instead of appending the lowest value to a new array, we exchange the lowest value with the ith value. Otherwise, Selection sort is conceptually the same as Simple sort except for the exchange.

Selection sort runs through the unsorted portion of the deck and exchanges the lowest card with the ith card.

Insertion sort doesn’t iterate through the unsorted portion. It merely takes the next card from the top of the unsorted portion and inserts it into the proper position in the ‘left hand’ sorted portion. This means the structure of the code changes such that although we still have an outer array to iterate through all the ‘cards’ in the deck, the inner array now iterates backwards through the sorted portion.

The Insertion sort takes the next card from the unsorted portion and moves it backwards through the sorted portion until it finds the correct position.

So with that review, let’s continue with Shell sort, invented by Shell in 1959. In this case, we have an example of the divide and conquer approach:

Sort every hth element of the array. For example, every 4th element. So if your array is 50 elements, create an array where the 0th element is less than the 3rd,  the first element is less than the 4th, the second element is less than the 5th and so on to the end.

When the array is sorted this way, it is called ‘h-sorted.’ The result is that in the end of the 4th h-sort, every 4th element is sorted with respect to the other elements in that subsequence.

Imagine you’re standing on the h-sorted array. If you start at the first element and move forward a step size of 4 elements — to the fourth one, the 8th one, the 12th one and so on —  you will always be stepping along a sorted array. If you start at the second element and move four more elements to the fifth one, and then the 9th one and then the 13th one, you will again be stepping along a sorted array. But if you misstep and move to a different subsequence, it won’t necessarily be sorted with respect to the path you were just on.

Now if we sort again with decreasing values of h, we can increase the speed of the overall sort. This is because each of these sorts can be implemented with only a few exchanges given that the previous ones happened.

The increased effeciency of this sort is not well defined. But it is thought to be a 20% to 40% better sort than insertion sort alone.

The code follows:

public func shellSort(a: [Double]) -> [Double] {

    var b = a

    let n = b.count

    var h = 1

    // Set h to the biggest reasonable value for an array of length n:

    while h < n/3 {

        h = 3*h + 1

    }

    var j = 0

    while h >= 1 {

        for i in h..<n {

            j = i

            while j >= h && b[j] < b[j-h] {

                b = exchange(a: b, i: j, j: j-h)

                j -= h

            }

        }

        h = h/3

    }

    return b

}

And this begs the question, if the Shell sort is 20-40% faster than Insertion sort alone, why doesn’t the Swift hybrid sort use the Shell sort instead of the Insertion sort for low values of n?