Thread: Hibbard Shell Sort

Try computing the values in the increment, then start running from the value that's gap size is less then the length of the array and work your way down to 1.

Going low to high would do this:

1. Sort with step size 1 (aka. basic insertion sort, O(n^2) worst performance)
2. Sort with step size 3 (already sorted, O(n))
3. Sorted with step size 5 (already sorted, O(n))
...

When you add up all of these performance times, it takes O(n^2 + n + n + n + ... + n), which technically boils down to O(n^2), but is considerable slower.

It's very easy to compute the step size:

for (int step = array.length() - array.length() % 2 - 1; i > 1; i -= 2)
{
    // insertion sort stuff with incrementing by step
}