Insertion sort much faster than shell sort

From a quick glance you can see that shell sort looks slower by having more loops. Brute force, you can put a system.out.println in the innermost loop to see how many comparisons are made.

3 Loops of shellsort

• for(int seqi = seqLen - 1; seqi >= 0; seqi--)
• for(int n = 0; n < length; n+=nth)
• while(j > 0 && a[j] < a[j - nth])

2 Loops of insertion

• for(int i = 1; i < length; i++)
• while(j > 0 && x < a[j-1])

Your implementation is broken and outputs the sorted array only due to the fact that the last step is 1 and your two internal cycles perform the basic insertion sort when the step is 1. When the step is greater then 1, the two internal cycles in your implementation do anything but step-sort the array, so what you implementation does is it shuffles the array in all iterations of the outer cycle and then insertion-sorts it in the last iteration of the outer cycle. Of course it will take longer then just insertion-sort it once.

Reusing your sequence the proper shell sort implementation should look like this:

public void sort( int[] a ) {
    int length = a.length;

    int stepIndex = 0;
    while ( stepIndex < SEQUENCE.length - 1 && SEQUENCE[ stepIndex ] < length / 3 ) {
        stepIndex++;
    }

    while ( stepIndex >= 0 ) {
        int step = SEQUENCE[ stepIndex-- ];
        for ( int i = step; i < length; i++ ) { // DIFF: i++ instead of i+=step
            for ( int j = i; j >= step && a[ j ] < a[ j - step ]; j -= step ) {
                exch( a, j, j - step );
            }
        }
    }
}

Two main differences between this implementation and yours:

• proper initial indexes for two internal cycles
• proper index increment for middle cycle (+1 instead of +step in your code)

Also, check the http://algs4.cs.princeton.edu/21elementary/Shell.java.html for a good implementation and good step sequence.