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.