Insert sort not working for large arrays

Question

I've written an insert sort and for my assignment I must be able to sort an array of size 10⁷. I've tested this sort with smaller arrays and it always sorts it correctly (up to size 10⁵). 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 10⁵ nothing would happen!

public static void insertSort(int[] arr){

        int x, y;
        for(y=1; y< arr.length; y++) {
            int temp = arr[y];
            x = y;
            while(x>0 && arr[x-1] >= temp){
                arr[x] = arr[x-1]; 
                --x;
            }
            arr[x] = temp;
        } 
}

Answer 1

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 < data.length; sortIndex++) {
        int temp = data[sortIndex];
        insertIndex = sortIndex;
        while (insertIndex > 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 < data.length; sortIndex++) {
        int temp = data[sortIndex];
        int insertIndex = sortIndex;
        while (insertIndex > 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 < data.length; sortIndex++) {
        int temp = data[sortIndex];
        int insertIndex = sortIndex;
        // find the insert point.
        while (insertIndex > 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 < data.length; sortIndex++) {
        int temp = data[sortIndex];
        int insertIndex = sortIndex;
        // find the insert point.
        while (insertIndex > 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 < data.length; sortIndex++) {
        int temp = data[sortIndex];
        insertIndex = sortIndex;
        while (insertIndex > 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 < data.length; sortIndex++) {
        int temp = data[sortIndex];
        int insertIndex = sortIndex;
        // find the insert point.
        while (insertIndex > 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[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);
    } 
}

When I run the following test on those functions, I get interesting results:

private static void runAll(int size) {
    final int[] data = new int[size];
    final int[] rand = buildData(size);

    System.arraycopy(rand, 0, data, 0, data.length);
    time("ACopy " + size, () -> insertSortArrayCopy(data));
    checkData(data);

    System.arraycopy(rand, 0, data, 0, data.length);
    time("Split " + size, () -> insertSortSplit(data));
    checkData(data);

    System.arraycopy(rand, 0, data, 0, data.length);
    time("Orig " + size, () -> insertSortOrig(data));
    checkData(data);

}

The above test (I call it with 10000) runs the three functions, yours, the one with ArrayCopy, and the one that has the sort in two parts.

It does not matter what order I run them in, but they all take an array of 10,000 random values, and sort them. The Times I get are:

Ran ACopy 10000 in 16.418ms
Ran Split 10000 in 10.262ms
Ran Orig 10000 in 24.080ms

What is that saying? It's saying that I can make the code run more than twice as fast, without changing the algorithm.... Now, if you are running your code in about 10 hours for \$10^7\$ then my improvements will bring it to... maybe 3 hours? That's a big difference.... but, wait, there's more.

Why does the 'split' function work so much faster than the single function? The reason is that the inside function gets called 10,000 times, and the outside function gets called once. A method that is called once is not 'compiled' by the Java compiler, but is run in more of an interpreted fashion. By putting the inner code in a function, the compiler sees it running many times, and it 'hotspot' compiles it.... with lots of optimization.

We can use that to our advantage.... If I take lots of small datasets (say 1000 data sets between 1 and 1000 members large, and I run those functions for those data sets, and then I run it for bigger data sets, by the time the big data set is run, the methods are 'hot' and compiled, and the Java machine is said to be 'warmed up'. What sort of difference does it make?

Well, for each of the three sorts above, let's see, first, your code:

Ran TenK Cold in 24.166ms
Ran TenK Hot in 9.689ms
Ran Warmup in 103.707ms
Ran Sort 1 in 0.002ms
Ran Sort 10 in 0.000ms
Ran Sort 100 in 0.002ms
Ran Sort 1000 in 0.178ms
Ran Sort 10000 in 9.379ms
Ran Sort 100000 in 915.304ms

The first run, of 10000 values, took 24ms. After a warmup, it took 9.5ms... and as part of the increasing data sizes, it took 9.5ms again.

Using arraycopy, it becomes:

Ran TenK Cold in 16.085ms
Ran TenK Hot in 8.073ms
Ran Warmup in 93.131ms
Ran Sort 1 in 0.003ms
Ran Sort 10 in 0.001ms
Ran Sort 100 in 0.003ms
Ran Sort 1000 in 0.169ms
Ran Sort 10000 in 7.520ms
Ran Sort 100000 in 837.687ms

Even 'hot', that has saved about.... 20%.

Now, as the split function....:

Ran TenK Cold in 10.250ms
Ran TenK Hot in 5.979ms
Ran Warmup in 78.793ms
Ran Sort 1 in 0.002ms
Ran Sort 10 in 0.001ms
Ran Sort 100 in 0.003ms
Ran Sort 1000 in 0.081ms
Ran Sort 10000 in 6.224ms
Ran Sort 100000 in 698.875ms

Now it is down to about 6ms, so, that's 30% off the original.... that's 'hot'. The cold version is even better.

Now, what if I used the native sort in Java (Arrays.sort(int[]))?

Well, that's impressive:

Ran TenK Cold in 2.576ms
Ran TenK Hot in 2.013ms
Ran Warmup in 75.236ms
Ran Sort 1 in 0.003ms
Ran Sort 10 in 0.002ms
Ran Sort 100 in 0.019ms
Ran Sort 1000 in 0.155ms
Ran Sort 10000 in 0.500ms
Ran Sort 100000 in 4.884ms

See how much better it scales \$O(n \log{n})\$? When you have the appropriate algorithm for the job it makes a real difference.

Answer 2

As this is a code review, you have to expect a review of other aspects than just performance, as such:

Variable names

Most people are okay with calling an array "arr", because you tend to be able to work out what arr means on the fly. "x" and "y" are less helpful, consider "sortIndex" and "insertIndex".

Abstraction

Currently this function will only sort an array of integers. Consider modifying it to support the List interface and use a Comparator, this way you can sort pretty much anything as long as it's in an order and a comparison exists.

public static <T> void insertSort(List<T> items, Comparator<T> comparer){
    int insertIndex, sortIndex;
    for(sortIndex=1; sortIndex< items.length; sortIndex++) {
        T temp = items[sortIndex];
        insertIndex = sortIndex;
        while(insertIndex > 0 && comparer.compare(items[insertIndex - 1], temp) >0{
            items[insertIndex] = items[insertIndex-1]; 
            --insertIndex;
        }
        items[insertIndex] = temp;
    } 
}