Now consider a different approach to sorting that grows the sorted set one element at a time. Select an arbitrary element from the unsorted set, and put it in the proper position in the sorted set.
InsertionSort(A)
for i = 1 to n-1 do
j=i
while (A[j] > A[j-1]) do swap(A[j],A[j-1])
Although insertion sort takes 
in the worst case,
it will perform considerably better if the data is almost
sorted, since few iterations of the inner loop will suffice to
sift it into the proper position.
Insertion sort is perhaps the simplest example of the incremental
insertion technique, where we build up a complicated structure on n
items by first building it on n-1 items and then making the necessary changes
to fix things in adding the last item.
Incremental insertion proves a particularly useful technique in geometric
algorithms.