Сортировка вставками

Сортировка вставками — простой алгоритм сортировки. У этого метода ряд преимуществ:

• прост в реализации;
• эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
• эффективен на наборах данных, которые уже частично отсортированы;
• это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
• может сортировать список по мере его получения;
• не требует временной памяти, даже под стек.

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора.

VBA

Sub Sort(Mus() As Long)
    Dim l As Long, r As Long, i As Long, j As Long, buf As Long
    l = LBound(Mus)
    r = UBound(Mus)
 
    For i = (l + 1) To r
        buf = Mus(i)
        j = i - 1
        Do While (Mus(j) > buf)
            Mus(j + 1) = Mus(j)
            If j = l Then Exit Do
            j = j - 1
        Loop
        Mus(j) = buf
    Next
End Sub

Паскаль

const N=255;
type array_type=array [1..N] of integer; 
 
procedure InsertSort(var x:array_type);
var
  i, j, buf:integer;
begin
  for i:=2 to N do
  begin
    buf:=x[i];
    j:=i-1;
    while (j>=1) and (x[j]>buf) do
    begin
      x[j+1]:=x[j];
      j:=j-1;
    end;
    x[j+1]:=buf;
  end;
end;

PHP

function insertion_sort(&$a) {
  // для каждого $a[$i] начиная со второго элемента...
  for ($i = 1; $i < count($a); $i++) {
    $x = $a[$i];
    for ($j = $i - 1; $j >= 0 && $a[$j] > $x; $j--) {
      /* сдвигаем элементы вправо, пока выполяется условие
         $a[$j] > $a[$i] */
      $a[$j + 1] = $a[$j];
    }
    // на оставшееся после сдига место, ставим $a[$i]
    $a[$j + 1] = $x;
  }
}