Bubble sort works by repeatedly stepping through the array, comparing each pair of adjacent items and swapping them if they are in the wrong order. The bubble sort algorithm executes in O(n²) time.

const proc: bubbleSort (inout array elemType: arr) is func
  local
    var boolean: swapped is FALSE;
    var integer: i is 0;
    var elemType: help is elemType.value;
  begin
    repeat
      swapped := FALSE;
      for i range 1 to length(arr) - 1 do
        if arr[i] > arr[i + 1] then
          help := arr[i];
          arr[i] := arr[i + 1];
          arr[i + 1] := help;
          swapped := TRUE;
        end if;
      end for;
    until not swapped;
  end func;

Cocktail sort is an improvement over Bubble Sort. The search for adjacent items with wrong order is done in both directions. The cocktail sort algorithm executes in O(n²) time.

const proc: cocktailSort (inout array elemType: arr) is func
  local
    var boolean: swapped is FALSE;
    var integer: i is 0;
    var elemType: help is elemType.value;
  begin
    repeat
      swapped := FALSE;
      for i range 1 to length(arr) - 1 do
        if arr[i] > arr[i + 1] then
          help := arr[i];
          arr[i] := arr[i + 1];
          arr[i + 1] := help;
          swapped := TRUE;
        end if;
      end for;
      if swapped then
        swapped := FALSE;
        for i range length(arr) - 1 downto 1 do
          if arr[i] > arr[i + 1] then
            help := arr[i];
            arr[i] := arr[i + 1];
            arr[i + 1] := help;
            swapped := TRUE;
          end if;
        end for;
      end if;
    until not swapped;
  end func;

Selection sort searches the minimum value in the array and swaps it with the value in the first position. After that the process is repeated for the remainder of the array. The selection sort algorithm executes in O(n²) time.

const proc: selectionSort (inout array elemType: arr) is func
  local
    var integer: i is 0;
    var integer: j is 0;
    var integer: min is 0;
    var elemType: help is elemType.value;
  begin
    for i range 1 to length(arr) - 1 do
      min := i;
      for j range i + 1 to length(arr) do
        if arr[j] < arr[min] then
          min := j;
        end if;
      end for;
      help := arr[min];
      arr[min] := arr[i];
      arr[i] := help;
    end for;
  end func;

Shaker sort is a variant of selection sort. It searches the minimum and maximum values in the array and swaps them with the values in the first and the last position respectively. After that the process is repeated for the remainder of the array. Note that the term shaker sort can also refer to cocktail sort, which is a variant of bubble sort. The shaker sort algorithm executes in O(n²) time.

const proc: shakerSort (inout array elemType: arr) is func
  local
    var integer: i is 1;
    var integer: j is 0;
    var integer: k is 0;
    var integer: min is 0;
    var integer: max is 0;
    var elemType: help is elemType.value;
  begin
    k := length(arr);
    while i < k  do
      min := i;
      max := i;
      for j range succ(i) to k do
        if arr[j] < arr[min] then
          min := j;
        end if;
        if arr[j] > arr[max] then
          max := j;
        end if;
      end for;
      help := arr[min];
      arr[min] := arr[i];
      arr[i] := help;
      if max = i then
        help := arr[min];
        arr[min] := arr[k];
        arr[k] := help;
      else
        help := arr[max];
        arr[max] := arr[k];
        arr[k] := help;
      end if;
      incr(i);
      decr(k);
    end while;
  end func;

Insertion sort forms a growing sorted list at the beginning of the array. Elements are removed from the array and then they are inserted into the correct position of the already-sorted list. The insertion sort algorithm executes in O(n²) time.

const proc: insertionSort (inout array elemType: arr) is func
  local
    var integer: i is 0;
    var integer: j is 0;
    var elemType: help is elemType.value;
  begin
    for i range 2 to length(arr) do
      j := i;
      help := arr[i];
      while j > 1 and arr[pred(j)] > help do
        arr[j] := arr[pred(j)];
        decr(j);
      end while;
      arr[j] := help;
    end for;
  end func;

Merge sort recognizes that a list with 0 or 1 elements is already sorted. Otherwise merge sort divides the unsorted list into two sublists of about half the size. Then each sublist is sorted by recursively calling merge sort. Afterwards the two sublists are merged into one sorted list. The merge sort algorithm executes in O(n log n) time.

const proc: mergeSort (inout array elemType: arr, in var integer: low, in integer: high) is func
  local
    var integer: mid is 0;
    var elemType: help is elemType.value;
    var integer: k is 0;
  begin
    if low < high then
      mid := (low + high) div 2;
      mergeSort(arr, low, mid);
      mergeSort(arr, succ(mid), high);
      incr(mid);
      while low < mid and mid <= high do
        if arr[low] < arr[mid] then
          incr(low);
        else
          help := arr[mid];
          for k range mid downto succ(low) do
            arr[k] := arr[pred(k)];
          end for;
          arr[low] := help;
          incr(low);
          incr(mid);
        end if;
      end while;
    end if;
  end func;

const proc: mergeSort (inout array elemType: arr) is func
  begin
    mergeSort(arr, 1, length(arr));
  end func;

const proc: mergeSort2 (inout array elemType: arr, in integer: low, in integer: high, inout array elemType: scratch) is func
  local
    var integer: mid is 0;
    var integer: k is 0;
    var integer: t_low is 0;
    var integer: t_high is 0;
  begin
    if low < high then
      mid := (low + high) div 2;
      mergeSort2(arr, low, mid, scratch);
      mergeSort2(arr, succ(mid), high, scratch);
      t_low := low;
      t_high := succ(mid);
      for k range low to high do
        if t_low <= mid and (t_high > high or arr[t_low] < arr[t_high]) then
          scratch[k] := arr[t_low];
          incr(t_low);
        else
          scratch[k] := arr[t_high];
          incr(t_high);
        end if;
      end for;
      for k range low to high do
        arr[k] := scratch[k];
      end for;
    end if;
  end func;

const proc: mergeSort2 (inout array elemType: arr) is func
  local
    var array elemType: scratch is 0 times elemType.value;
  begin
    scratch := length(arr) times elemType.value;
    mergeSort2(arr, 1, length(arr), scratch);
  end func;

const proc: downheap (inout array elemType: arr, in var integer: k, in integer: n) is func
  local
    var elemType: help is elemType.value;
    var integer: j is 0;
  begin
    if k <= n div 2 then
      help := arr[k];
      repeat
        j := 2 * k;
        if j < n and arr[j] < arr[succ(j)] then
          incr(j);
        end if;
        if help < arr[j] then
          arr[k] := arr[j];
          k := j;
        end if;
      until help >= arr[j] or k > n div 2;
      arr[k] := help;
    end if;
  end func;

const proc: heapSort (inout array elemType: arr) is func
  local
    var integer: n is 0;
    var integer: k is 0;
    var elemType: help is elemType.value;
  begin
    n := length(arr);
    for k range n div 2 downto 1 do
      downheap(arr, k, n);
    end for;
    repeat
      help := arr[1];
      arr[1] := arr[n];
      arr[n] := help;
      decr(n);
      downheap(arr, 1, n);
    until n <= 1;
  end func;

const proc: shellSort (inout array elemType: arr) is func
  local
    var integer: i is 0;
    var integer: j is 0;
    var integer: increment is 0;
    var elemType: help is elemType.value;
  begin
    increment := length(arr) div 2;
    while increment > 0 do
      for i range 1 to length(arr) do
        j := i;
        help := arr[i];
        while j > increment and arr[j - increment] > help do
          arr[j] := arr[j - increment];
          j -:= increment;
        end while;
        arr[j] := help;
      end for;
      increment := increment div 2;
    end while;
  end func;

const proc: quickSort (inout array elemType: arr, in integer: left, in integer: right) is func
  local
    var elemType: compare_elem is elemType.value;
    var integer: less_idx is 0;
    var integer: greater_idx is 0;
    var elemType: help is elemType.value;
  begin
    if right > left then
      compare_elem := arr[right];
      less_idx := pred(left);
      greater_idx := right;
      repeat
        repeat
          incr(less_idx);
        until arr[less_idx] >= compare_elem;
        repeat
          decr(greater_idx);
        until arr[greater_idx] <= compare_elem or greater_idx = left;
        if less_idx < greater_idx then
          help := arr[less_idx];
          arr[less_idx] := arr[greater_idx];
          arr[greater_idx] := help;
        end if;
      until less_idx >= greater_idx;
      arr[right] := arr[less_idx];
      arr[less_idx] := compare_elem;
      quickSort(arr, left, pred(less_idx));
      quickSort(arr, succ(less_idx), right);
    end if;
  end func;

const proc: quickSort (inout array elemType: arr) is func
  begin
    quickSort(arr, 1, length(arr));
  end func;