Insertion Sort

Sorting has been a very basic need in the world of programming. Insertion sort, for me is a very basic sorting technique. For anyone who plays cards, this is quite simple. Imagine, you are picking card one by one from right hand, and placing them in the correct position in your left hand. This is the very basis of this technique. 

Lets start by defining a pseudo code.

Psuedo Code

for j = 2 to A:length
 	key = A[j]
 	i = j - 1
 	while i > 0 and A[i] > key
 		A[i + 1] = A[i]
 		i = i - 1
 	A[i + 1] = key

Explanation

The above process explains the concept in detail.

We always start with the second number and consider it as a key. After every iteration of the loop, the left hand side of the key should be sorted and right hand is the unsorted list.

Now, for each iteration, our goal is to put the key to its correct position on the left. 

let's compare the key with the element on the left. If the key is smaller then the position of key needs to be changed. We'll move continuously to the left and move the numbers in current pass to a place to current pass + 1, until we have find a spot such that key is higher than the number it is compared to or we have reached the start of the list. Insert the key now to the current pass + 1.

Java Code

for (int i = 1; i < A.length; i++) {
	int key = A[i];

	int j = i - 1;
			
	while (j >= 0 && A[j] > key) {
		A[j + 1] = A[j];
		j--;
	}

	A[j + 1] = key;
}

you can view the complete code in github.