KNOWLEDGE BASE
Log In    |    Knowledge Base    |    4D Home
Tech Tip: Insertion Sort Algorithm
PRODUCT: 4D | VERSION: 2003.2 | PLATFORM: Mac & Win
Published On: March 11, 2004
Your current browser may not allow you to download the asset. We recommend Mozilla Firefox or Google Chrome.
Log In

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