Insertion Sort

  Insertion sort is like picking a card from a set of unsorted cards and comparing it
  to all the cards present on the left for higher or smaller values and inserting this
  card into right position. After every pass, the picked value reaches at its right position.
 
  for e.g.
  input : 10,5,3,4,12,1,13
  after First Pass :
  -> 5,10,3,4,12,1,13
  after Second Pass:
  -> 3,5,10,4,12,1,13
  after Third Pass:
  -> 3,4,5,10,12,1,13
  in fourth pass when the pointer is pointing to 12 there is not need to move it since
  it is already greater than the immediate next element i.e. 10:
  -> 3,4,5,10,12,1,13
  after fifth Pass:
  -> 1,3,4,5,10,12,13
  in sixth pass also there is no need to move the elements
  and you get your output
 
  It's time complexity is O(n^2) but still it performance much faster than bubble sort and
  slightly better than selection sort.
 
  Below is the code for same.


public class InsertionSort {

public static void main(String[] args) {
int[] arr = {10,5,3,4,12,1,13,2,50,1,11,6,9,0,12,3,87,27};
int temp = 0;
int k=0;
for(int i=1;i< arr.length;i++){
k= i-1;
if(arr[k]>arr[i]){
temp = arr[i];
while(k>=0 && arr[k]> temp){
arr[k+1] = arr[k];
k--;
}
arr[k+1] = temp;
}

}
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}

}