InsertionSort ( list, N )
//list: list of elements to be sorted from index 1 to N
//N:	 number of elements in list

for i=2 to N do //elements to be inserted  
  newElement=list[i]
  location=i-1
  while (location >= 1 and list[location] > newElement) 
	//move any larger elements out of the way
     list[location+1]=list[location]
     location = location - 1
  end while
list[location+1] = newElement
end for