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.
for i = 1 to n-1 do
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.