Insertion Sort

Insert sort can be understood using the analogy of playing game of cards like rummy. In the cards game , initially we get some x number of cards. We take these cards and sort them in our hands from left to right in ascending order. After this we start the playing where as and when we get a new card, we take that card, start comparing it from right to left in our hands and insert this new card wherever it fit as per it value. This is insertion sort.

In case of sorting an array using insertion sort, we basically start from position 1 and compare it with position 0. Swap these positions --> smaller goes left and bigger goes right. After this move on to position 2 and compare it with both position 0 & 1 and insert element at position 2 where it should and again repeat the same process till we complete the whole array.

 public static int[] doInsertionSort(int[ ] input){

         

        int temp;

        for (int i = 1; i < input.length; i++) {

        System.out.println("This is the value " + i);

            for(int j = i ; j > 0 ; j--){

            System.out.println("This is the value " + i);

                if(input[j] < input[j-1]){

                    temp = input[j];

                    input[j] = input[j-1];

                    input[j-1] = temp;

                }

            }

        }

        return input;

    }

Efficiency :-

Efficiency of insertion sort is O(N*N), however, if most of the data in a list/array is almost sorted, than it works very first.Good for list/array which are slightly out of order.