insertion_sort

INSERTION-SORT(Array)
   for i = 1 to n
   	key ← Array[i]
    	j ← i – 1
  	 while j > = 0 and Array[j] > key
   		Array[j+1] ← Array[j]
   		j ← j – 1
   	end while 
   	Array[j+1] ← key
  end for