Can this insertion sort be optimized?

Question

Could you provide feedback for this code? For arrays of length 2, is it more efficient not to use a sorting algorithm?

package insertion.sort;

import java.util.Arrays;

public class InsertionSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int[] testArr = {-10, -5, 100, 51, 6, 50};
        insertionSort(testArr);
        System.out.println(Arrays.toString(testArr));
    }

    public static void insertionSort(int[] arr) {
        for(int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for(j = i; j > 0 && arr[j-1] > temp; j--)
                arr[j] = arr[j-1];
            arr[j] = temp;
        }
    }

}

By the way, I've noticed "quicksort" is spelt all as one word, but "insertion sort" is spelt as two. Is that right? Would anyone ever say "quicksort sort"?

Answer 1

Minor issues

• The word "insertion" in the method name insertionSort is redundant: it's already in the class name

• The Javadoc for the main method is pointless, it would be better to remove

• Perhaps you did it this way for the sake of an example, but the main method would be better in another class, not InsertionSort itself.

Generalizing

It might be good to generalize the class so that it can sort anything, not only integers. Perhaps something like this:

public class InsertionSort<T extends Comparable<T>> {    
    public void sort(T[] arr) {
        for (int i = 1; i < arr.length; i++) {
            T temp = arr[i];
            int j;
            for (j = i; j > 0 && arr[j - 1].compareTo(temp) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
}

class InsertionSortDemo {
    public static void main(String[] args) {
        Integer[] ints = {-10, -5, 100, 51, 6, 50};
        new InsertionSort<Integer>().sort(ints);
        System.out.println(Arrays.toString(ints));

        String[] strings = {"hello", "there", "my", "friend"};
        new InsertionSort<String>().sort(strings);
        System.out.println(Arrays.toString(strings));
    }
}

Answer 2

As insertion sort is an O(n²) algorithm, there's not much point to optimizing it. For any input that is large enough for you to care about the performance, you would want to pick a sorting algorithm with better bounds. Quicksort, for example, is usually closer to O(n log n).

That said, I'll point out some style issues:

• You should never omit optional braces, as you've done for the inner for-loop. Think of it this way: anytime you omit braces, you're a contributing factor to a future coding accident. (Apple learned this lesson the hard way; their new swift language requires braces.)
• Variables can usually be named better than "temp". Renaming temp to elementToInsert, for example, would make your code self-documenting.

Answer 3

I do not see any performance issues. Stylistically, a No Raw Loops rule mandates factoring out an inner loop into a method (shift_right or something like that).