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