Is this Shell sort?

Question

Trying to learn shell sort, I kinda understood what wikipedia was trying to say, but I wanted a bit of confirmation, so I went on youtube, here, but this code does not work and does not look like what I read on wikipedia. I go to hi's website just in case I misspelled anything to copy+paste hi's code, nop not working either.

So here is my version, or rather what I understood of it. It does work (as in it gives me a correctly sorted array) but I'm not 100% sure this is even shell sort, or is it ? I don't know.

public int[] shellSort(int[] numbers, compare compare) {

    int firstPivot, secondPivot, temp;
    int interval = numbers.Length / 2;

    while (interval > 0) {

        System.Diagnostics.Debug.WriteLine(interval);


        // Start from interval, go all the way to the end
        for (secondPivot = interval; secondPivot < numbers.Length; secondPivot++) {

            firstPivot = secondPivot;
            temp = numbers[secondPivot];

            // Compare with predecesors from interval to interval
            while ((firstPivot - interval >= 0) && compare(temp, numbers[firstPivot - interval])) {

                numbers[firstPivot] = numbers[firstPivot - interval];
                firstPivot -= interval;

            }

            // At the end we find the almost correct position for our "secondPivot" number
            numbers[firstPivot] = temp;

        }

        // Decrease interval
        interval = interval / 2;
    } // Untill interval is "1" then we practically get an insertion sort that cleans up 
      // and have a properly sorted array

    return numbers;
}

Answer 1

First, the good points: your code is quite cleanly written. Although some may argue over the naming convention(s) you've chosen, your names are reasonable, readable, and you do seem to have followed the naming convention fairly consistently.

At least if I'm reading it correctly, yes, this does implement a Shell sort. Unfortunately, however, it uses a sequence of gap values (powers of 2) that is known to be fairly inefficient. With the right sequence, Shell-sort can give around O(N^1.2). There are a couple of fairly easy sequences to generate that give only somewhat worse than that (around N^1.3 to N^1.5). Although I don't believe a theoretical basis for it is known, the best sequences mostly follow ratios of around 2.2 to 2.25 or so.

Starting with N/2 doesn't seem to be the best choice either. At least in most cases, starting somewhere around N/3 (or smaller) tends to work better.