Цикличная сортировка

Возьмём элемент. Найдём для него подходящее место в массиве. Поместим элемент в найденное место, а элемент, который занимал нужное нам место, извлечём и поищем нововое расположение теперь для него... Продолжаем, пока на найдётся элемент, который нужно положить на место того, с которого мы начали. Круг замкнулся.

Повторим такие циклы для каждого элемента массива слева направо. 

На i-й итерации все элементы левее i-го уже стоят на своих местах. Анализировать нужно только тех, кто правее i-й позиции.

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

type
  TAI = array of integer;
...
procedure CycleSort(var A: TAI);
var
    i: integer;
    buf: integer; // Буфер для элемента, которому мы ищем место.

    // Один шаг алгоритма.
    // StartPos - Начальная позиция в массиве.
    //             Всё что левее, уже отсортировано.
    // Buffer - значение элемента, которому ищем место.
    // Функция найдёт новое место в массиве A для значения Buffer и поместит
    //  его туда, а ранее находившийся там элемент вернёт в Buffer.
    // First - признак первого прохода в итерации. Если элемент уже стоит на своём месте,
    //  дальнейшие действия не нужны и можно сразу переходить к следующей итерации.
    function Step(StartPos: integer; var Buffer: integer;
                  First: boolean): integer;
    var
        j: integer;
    begin
      // Ищем правильное место для значения Buffer
      result := StartPos;
      for j := StartPos+1 to High(A) do
        if A[j] < Buffer then inc(result);
      // Если элемент уже на правильном месте на первом шаге в итерации,
      //  мы закончили.
      if First and (result = StartPos) then Exit;

      // Если в выбранном месте находятся дубликаты элемента Buffer,
      //  разместимся сразу после них.
      while Buffer = A[result] do
        inc(result);

      // Обменяем значения Buffer и выбранного элемента.
      swap(Buffer, A[result]);
    end;

begin
  // Для всех элементов массива.
  for i := Low(A) to High(A)-1 do
  begin
    // Отложим текущий элемент в буфер.
    buf := A[i];
    // Если элемент в буфере не на своём месте,
    if Step(i, buf, true) <> i then
      // продолжаем цикл пока очередной элемент не окажется на месте
      //  стартового элемента этой итерации.
      while Step(i, buf, false) <> i do ;
  end;
end;

Большое количество сравнений обычно делает этот алгоритм не слишком эффективным. Его область применения - задачи в которых велика стоимость записи в массив. Количество перестановок в этом алгоритме минимально.

Сложность: