Insertion Sort: Code

for i:= 2 to n do

x := L[i];

j := i-1;

while jɘ and x < L[j] do

L[j-1] := L[j];

j := j-1;

endwhile

L[j+1] := x;

endfor

Fixed n-1 iterations

Worst case i-1 comparisons