## Insertion Sort

Another method of sorting, where the sorting is performed by storing successive records K2, K3….KN-1 into some temporary variable.

Value of this temporary variable is successively compared with the other values.

Procedure INSERTION_SORT(K, N).

Given a vector K of N elements, this procedure rearranges the vector in ascending order. I and J are loop variables. Y is the temporary variable that holds the element to be inserted.  All variables are integer.

K – Vector array to be sorted

N – Size fo the array

I, J – Loop variables

Y – Temporary variable holding an element to be inserted

1)    [Set the loop]

Repeat thru step 5 for I = 2, 3, ……, N

2)    [Store element to be compared at temporary position]

Y <- K[I]

3)    [Initialize the comparison]

J <- I – 1

4)    [Set the comparison loop]

Repeat while J >= 1 and Y < K[J]

K[J+1] <- K[J]

J <- J – 1

5)    [Copy temporary stored value to appropriate position]

K[J+1] <- Y

6)    [Finish]

Return

### Tracing In a insertion Sort Total no of Passes = Total No of  Elements .

In each pass a piece of the elements list will br consider in the last pass a complete element list will be consider.

#### About the Author 