InsertionSort vs ShellSort with Gap Size = 1?

Question

I have two implementations for two different sorts, InsertionSort and ShellSort.

They are as follows:

InsertionSort:

for (int pos = 0; pos < arrayToBeSorted.length; pos++) {
    for (int secondMarker = pos; secondMarker > 0; secondMarker--) {
        int currentValue = arrayToBeSorted[secondMarker];
        int valueBeingCheckedAgainst = arrayToBeSorted[secondMarker - 1];
        if (currentValue > valueBeingCheckedAgainst) {
            break;
        }
        arrayToBeSorted[secondMarker] = arrayToBeSorted[secondMarker - 1];
        arrayToBeSorted[secondMarker - 1] = currentValue;
    }
}

ShellSort:

for (int gap = a.length / a.length; gap > 0; gap = (gap / 2)) {
    for (int i = gap; i < a.length; i++) {
        int tmp = a[i];
        int j = i;
        for (; j >= gap && tmp < (a[j - gap]); j -= gap) {
            a[j] = a[j - gap];
        }
        a[j] = tmp;
    }
}

I also have 10 array of integers which hold 32000 integers. I get the time before I call the static sortArray methods in these classes. Here are the results:

For InsertionSort.sortArray:

Solving array with: 32000 elements.
Time in milliseconds:264
Time in milliseconds:271
Time in milliseconds:268
Time in milliseconds:263
Time in milliseconds:259
Time in milliseconds:257
Time in milliseconds:258
Time in milliseconds:260
Time in milliseconds:259
Time in milliseconds:261

And for ShellSort:

Solving array with: 32000 elements.
Time in milliseconds:357
Time in milliseconds:337
Time in milliseconds:167
Time in milliseconds:168
Time in milliseconds:165
Time in milliseconds:168
Time in milliseconds:167
Time in milliseconds:167
Time in milliseconds:166
Time in milliseconds:167

So how come there is so much difference between them? They are basically the same algorithms?

Also, how is it possible that the first 2 runs for ShellSort takes longer, but the rest is quicker?

This is the results for 128000 elements, InsertionSort first again:

Solving array with: 128000 elements.
Time in milliseconds:4292
Time in milliseconds:4267
Time in milliseconds:4241
Time in milliseconds:4252
Time in milliseconds:4253
Time in milliseconds:4248
Time in milliseconds:4261
Time in milliseconds:4260
Time in milliseconds:4333
Time in milliseconds:4261

ShellSort:

Solving array with: 128000 elements.
Time in milliseconds:5358
Time in milliseconds:5335
Time in milliseconds:2676
Time in milliseconds:2656
Time in milliseconds:2662
Time in milliseconds:2654
Time in milliseconds:2661
Time in milliseconds:2656
Time in milliseconds:2660
Time in milliseconds:2673

I am sure that the arrays are I am passing to the methods are exactly same and they are quite random.

Answer 1

In your insertion sort, you are being more complicated,

for (int pos = 0; pos < arrayToBeSorted.length; pos++) {
    for (int secondMarker = pos; secondMarker > 0; secondMarker--) {
        int currentValue = arrayToBeSorted[secondMarker];
        int valueBeingCheckedAgainst = arrayToBeSorted[secondMarker - 1];
        if (currentValue > valueBeingCheckedAgainst) {
            break;
        }
        arrayToBeSorted[secondMarker] = arrayToBeSorted[secondMarker - 1];
        arrayToBeSorted[secondMarker - 1] = currentValue;
    }
}

You read the value from the array in the inner loop, and while the value at the preceding position is not smaller, you write two values to the array.

In the shell sort,

for (int i = gap; i < a.length; i++) {
    int tmp = a[i];
    int j = i;
    for (; j >= gap && tmp < (a[j - gap]); j -= gap) {
        a[j] = a[j - gap];
    }
    a[j] = tmp;
}

you read the value to be placed once, outside the inner loop, and only have a single write in the inner loop body, writing the value only once after the inner loop.

That is more efficient, and so it's understandable that the shell sort is faster. That the two first shell sorts are slower is probably because the wrapping

for (int gap = a.length / a.length; gap > 0; gap = (gap / 2)) {

confuses the JIT for a while before it notices that gap can be replaced with 1 and the wrapping loop eliminated.