Insertion Sort is a simple sorting algorithm that functions like its name suggests. It goes through the array checking the current index with the previous index to see if the current element in the index is less than that of the element in the previous indexes. If it finds an element in the current index to be smaller than that of the element in the previous indexes, it will locate the position where that occurs and insert the current element into that position. The Insertion Sort algorithm is proficient with lists of a few thousand items or less. Its performance decreases with lists greater than a few thousand items. Like the Bubble Sort the complexity is O(n2) but the Insertion Sort is twice as fast. Below is a basic Insertion Sort algorithm:

ARRAY LONGINT($Array;10)
C_LONGINT($i;$j;$index)

For ($i;1;Size of array($Array))
  $index:=$Array{$i}
  $j:=$i
  While (($j>0) & ($Array{$j-1}>$index))
    $Array{$j}:=$Array{$j-1}
    $j:=$j-1
  End while
  $Array{$j}:=$index
End for