Java insertion sort implementation

Question

I have written code for insertion sort. I just want some feedback whether the above implementation is correct and can be improved.

public class InsertionSortNew {
 static int temp;
 public static void InsertionSort(int [] array){
 for(int i =0;i<=array.length-1;i++){
 int key = array[i];
 for(int j=i-1;j>=0;j--){
 if(key<array[j]){
 temp = key;
 array[j+1] = array[j];
 array[j] = key;
 key = array[j];
 }else{
 break;
 }
 }
 }
 }

Answer 1

Code

First of all, please avoid having a static int temp: in case two or more threads call your insertion sort, they will interfere. Also, I would declare the constructor as private:

private InsertionSortNew() {}

Style

You abuse your code with empty lines. Usually people put empty lines before and after conditional blocks (if) and loops (for, while).

Performance

You can prune away like 60% of assignments in the inner loop as follows: first, you store the element being inserted; next, until sorted you keep moving the preceding larger integers one position to the right, and finally, you put the cached element into its correct position.

All in all, I had this in mind:

private InsertionSortNew() {}
public static final void sort(int [] array){
 for (int i = 1; i < array.length; ++i) {
 int key = array[i];
 int j;
 for (j = i - 1; j >= 0 && array[j] > key; --j) {
 array[j + 1] = array[j];
 }
 array[j + 1] = key; 
 }
}

..., which gives me these performance figures:

Original version took 2281.41 milliseconds.
rodde's version took 1581.65 milliseconds.
Equals: true