Insertion Sort

In Insertion sort, first select a key and insert it at its correct position.

Steps:
1. Select one key in each iteration starting from 2nd element(1st index)
2. Now compare the key with all its previous elements, starting from [keyPos-1] index.
Store the key in a temp variable.
At any index, if the key is less than the element at that index, move that element to its next position.
Continue this till 0th index.
3. By this time/earlier, key's index will be decided.
So place the key at that index.
4. Repeat the steps 2 and 3 for next indices.

Code:

import java.util.Arrays;

class InsertionSort {
        static public void insertionSort(int[] a) {
                int len = a.length;

                for(int i=0; i<len; i++) {
                        int key = a[i];

                        int j = i;

                        while(j>0 && a[j-1] > key) {
                                a[j] = a[j-1];
                                j--;
                        }

                        a[j] = key;
                }
        }

        static public void main(String[] args) {
                int[] in = {6, 8, 1, 4, 5, 3, 7, 2};

                System.out.println(Arrays.toString(in));

                insertionSort(in);

                System.out.println(Arrays.toString(in));
        }
}

eg:

Input: 6 8 1 4 5 3 7 2

1st iteration:

key = 8

compare 6 & 8: 6 < 8. Dont move.

2nd iteration:

key = 1

compare 8 & 1: 8 > 1. So move 8 to its next position.

==> 6 8 8 4 5 3 7 2

Now compare 6 & 1: 6 > 1. So move 6 to its next position.

==> 6 6 8 4 5 3 7 2

Now we are at index 0. So replace 0th index element with key

==> 1 6 8 4 5 3 7 2

....

....

Complexity Analysis: TODO