The Bubble Sort is the simplest sorting algorithm in use. Under the best case condition where the array is in sorted order the level of complexity is O(n). Normally the complexity level is O(n2).

The way the Bubble Sort works is by comparing each element in an array (n) with the previous element in the array (n-1). If it finds that the n element in the array is greater than the n-1 element in the array, it will swap the two. The algorithm repeats this process until it passes through the entire array. As it passes through the array, the smaller element (n) gets de-incremented through the array (n-i > 0). This causes larger values to move to the end of the array while smaller values move towards the beginning of the array.

Below is a sample of the Bubble Sort method written in 4D:

For ($i;1;Size of array($array))
  For ($j;1;Size of array($array)-$i)
    If ($array {$j+1}<$array {$j})
      $tmp:= $array {$j}
      $array {$j}:=$array {$j+1}
      $array {$j+1}:=$tmp
    End if
  End for
End for