Рассмотрим еще один алгоритм сортировки - сортировка вставкой. Идея его заключается в следующем: начиная со второго элемента массива, по очереди будем "продвигать" текущий элемент к началу массива, пока этот элемент не окажется первым в массиве или его значение будет меньше значения впереди стоящего элемента.

Pascal Реализация:

for i := 2 to n begin
  k := i;
  // "Продвигаем" k-й элемент к началу массива
  while (k > 1) and (a[k] < a[k - 1]) begin
    // Меняем местами текущий элемент с впереди стоящим "соседом"
    temp := a[k];
    a[k] := a[k - 1];
    a[k - 1] := temp;
    k := k - 1;
   end;
end;

C/C++ реализация:

for (int i = 1; i < n; ++i) {
  int k = i;
  // "Продвигаем" k-й элемент к началу массива
  while (k > 0 && a[k] < a[k - 1]) {
    // Меняем местами текущий элемент с впереди стоящим "соседом"
    int temp = a[k];
    a[k] = a[k - 1];
    a[k - 1] = temp;
    --k;
  }
}