Insert sort not working for large arrays

I've written an insert sort and for my assignment I must be able to sort an array of size 107. I've tested this sort with smaller arrays and it always sorts it correctly (up to size 105). If I make the array any bigger and try to output the sorted array nothing happens (I've waited 15 minutes just in case it was just talking long).

I was wondering if anybody had any information on how to fix this. Maybe my code is just wrong or maybe I should be using something different.

This is the code for my sort. I've shuffled different sized arrays and it always gave the sorted array correctly though as stated before once an array was bigger than 105 nothing would happen!

public static void insertSort(int[] arr){

        int x, y;
        for(y=1; y0 && arr[x-1] >= temp){
                arr[x] = arr[x-1]; 
                --x;
            }
            arr[x] = temp;
        } 
}

This would be a good opportunity to learn some performance features and limitations of the Java Virtual Machine, and the available libraries.

I want to take your code, go through a staged progression of optimizations that will improve the way the code performs, and, while it will not change the runtime 'complexity' \$O(n^2)\$ of the insertion sort, it will improve the actual runtime.

As Nick has suggested, your variable names are not very meaningful. He's suggested insertIndex and sortIndex. I can use those, they are good. So your code becomes:

public static void insertSort(int[] data) {
    int insertIndex, sortIndex;
    for (sortIndex = 1; sortIndex  0 && data[insertIndex - 1] >= temp) {
            data[insertIndex] = data[insertIndex - 1];
            --insertIndex;
        }
        data[insertIndex] = temp;
    }
}

Now, I also changed arr to data, and I added space around the operators and between loop keywords and braces. But, the above, is really your code, reformatted.

After that neatening up, there is one more things that need to happen: Variable scopes. Variables should be as narrow as possible. The sortIndex should be declared as part of the for loop control system, and the insertIndex should be declared inside the loop.

This is the result:

public static void insertSort(int[] data) {

    for (int sortIndex = 1; sortIndex  0 && data[insertIndex - 1] >= temp) {
            data[insertIndex] = data[insertIndex - 1];
            --insertIndex;
        }
        data[insertIndex] = temp;
    }
}

Now, that's a good looking insertion sort.... but, can it go faster? Yes.

The insertion sort is basically an operation where you identify where the data belongs, and then you shift all the larger data to the right, and insert the value. The code above shifts the values one at a time. If you identify the position, and shift them all at once, using an optimized system, you get better results. First, an intermediate result:

public static void insertSort(int[] data) {

    for (int sortIndex = 1; sortIndex  0 && data[insertIndex - 1] >= temp) {
            --insertIndex;
        }
        // shift the values
        for (int i = sortIndex; i > insertIndex; i--) {
            data[i] = data[i - 1];
        }
        data[insertIndex] = temp;
    }
}

Now, that may not look faster, and you're right, it is probably not faster, but, if we replace the second loop with:

public static void insertSort(int[] data) {

    for (int sortIndex = 1; sortIndex  0 && data[insertIndex - 1] >= temp) {
            --insertIndex;
        }
        // shift the values
        System.arraycopy(data, insertIndex, data, insertIndex + 1, sortIndex - insertIndex);
        data[insertIndex] = temp;
    }
}

Now, we're cooking. How much, though?

Before we get there, I am going to suggest another change, which is to take the insides of the loop, and make it another function too, and also make some variables 'final', so the code looks like:

private static final void subInsertSort(final int[] data, final int sortIndex) {
    final int temp = data[sortIndex];
    int insertIndex = sortIndex - 1;
    while (insertIndex >= 0 && temp < data[insertIndex]) {
        insertIndex--;
    }
    insertIndex++;
    System.arraycopy(data, insertIndex, data, insertIndex + 1, sortIndex - insertIndex);
    data[insertIndex] = temp;
}

public static void insertSortSplit(final int[] data){

    for(int sortIndex = 1; sortIndex < data.length; sortIndex++) {
        subInsertSort(data, sortIndex);
    } 
}

I know, you're going to ask "Why?"... let me get to that.

I took the liberty of writing a quick test, on my system, that looks like:

private static final long time(String name, Runnable torun) {
    long nanos = System.nanoTime();
    torun.run();
    long time = System.nanoTime() - nanos;
    System.out.printf("Ran %s in %.3fms%n", name, time / 1000000.0);
    return time;
}

Now, that's got some Java8 stuff in it, but, all it really does, is time how long it takes to run a function. If I have the following 3 functions though (all do the same thing, with different names:

```
public static void insertSortOrig(int[] data) {
int insertIndex, sortIndex;
for (sortIndex = 1; sortIndex 0 && data[insertIndex - 1] >= temp) {
data[insertIndex] = data[insertIndex - 1];
--insertIndex;
}
data[insertIndex] = temp;
}
}

public static void insertSortArrayCopy(int[] data) {

for (int sortIndex = 1; sortIndex 0 && data[insertIndex - 1] >= temp) {
--insertIndex;
}
// shift the values
System.arraycopy(data, insertIndex, data, insertIndex + 1, sortIndex - insertIndex);
data[insertIndex] = temp;
}
}

private static final void subInsertSort(final int[] data, final int sortIndex) {
final int temp = data[sortIndex];
int insertIndex = sortIndex - 1;
while (insertIndex >= 0 && temp < data[inse

StackExchange Code Review Q#64508, answer score: 10