Insertion Sort

Insertion Sort

Insertion Sort

Suppose A is an array of N values. We want to sort A in ascending order.

Insertion Sort is an algorithm to do this as follows: We traverse the array and insert each element into the sorted part of the list where it belongs. This usually involves pushing down the larger elements in the sorted part.

     For I = 1 to N-1
       J = I
       Do while (J > 0) and (A(J) < A(J - 1)
         Temp = A(J)
         A(J) = A(J - 1)
         A(J - 1) = Temp
         J = J - 1 
       End-Do
     End-For
Insertion Sort does roughly N**2 / 2 comparisons and does up to N - 1 swaps.