InsertionSort.java

public class InsertionSort {

    public int[] sort(int[] input) {
        int[] output = new int[input.length];

        for (int i=0; i<input.length; i++) {
            int indexToInsert = 0;
            for (int j=0; j<=i; j++) {
                if (input[i] < output[j]) {
                    indexToInsert=j;
                    break;
                }
            }

            // move i to i+1 from j
            for (int j= i-1; j>=indexToInsert; j--) {
                output[j+1] = output[j];
            }

            output[indexToInsert] = input[i];
        }
        return output;
    }

    public void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i);
            System.out.print("\t");
        }
        System.out.print("\n");
    }

    public static void main(String[] args) {
        int[] input = {5,4,1,3,2};
        InsertionSort insertionSort = new InsertionSort();
        insertionSort.printArray(input);

        // Sort
        insertionSort.printArray(insertionSort.sort(input));
    }
}