Сортировка Ханойская башня.

Сохраняем общую идею рекурсивного алгоритма решения Ханойских башен.

В отличии от классической головоломки, на первом этапе проведём "нормализацию". Наполним одну башню несортированной последовательностью элементов и будем выполнять алгоритм ханойских башен над частью этой башни, пока элементы в ней не закончатся. В двух других башнях элементы всегда будут отсортированы в силу особенностей алгоритма решения ханойских башен.

На последнем этапе останется только объединить две полученных упорядоченных последовательности.

type
  TAI = array of integer;
...
procedure HanoiSort(var A: TAI);
var
    // Три столбика для ханойских башен.
    W: Array [0..2] of TList<integer>;
    i: integer;
    ia,ib,ic: integer; // Текущие номера башен A, B и C.
    k, n: integer;

    // Классический алгоритм ханойской башни.
    // Переносим n элементов сверху из башни номер source в target
    //  используя как промежуточную башню helper.
    procedure hanoi(n: integer; source, target, helper: integer);
    begin
      if n=1 then
      begin
        W[target].Add(W[Source].Items[W[Source].Count-1]);
        W[Source].Delete(W[Source].Count-1);
      end
        else
      begin
        hanoi(n - 1, source, helper, target);
        hanoi(1, source, target, helper);
        hanoi(n - 1, helper, target, source);
      end;
    end;

    // Переносим из башни B в башню C все элементы, которые меньше
    //  или равны верхнему элементу башни C.
    procedure B2C;
    var
        n: integer;
    begin
      n := 0;
      while (W[ib].Count-1 - n >= 0) and
            (W[ib].Items[W[ib].Count-1 - n] <= W[ic].Items[W[ic].Count-1])  do
      begin
        inc(n);
      end;
      if n>0 then hanoi(n, ib, ic, ia);
      // Меняем местами башни B и C.
      swap(ib, ic);
    end;

begin
  // Создаём башни.
  for i := Low(W) to High(W) do
    W[i] := TList<integer>.Create;
  ia := 0;
  ib := 1;
  ic := 2;

  // Наполняем башню A исходным массивом.
  for i := Low(A) to High(A) do
    W[ia].Add(A[i]);

  // Нормализуем порядок элементов.
  while (W[ia].Count>0) do
  begin
      k := W[ia].Items[W[ia].Count-1];
    // Классический алгоритм для группы элементов,
    //  которые меньше верхнего элемента A.
    while (W[ic].Count>0) and (W[ic].Items[W[ic].Count-1] < k) do
    begin
      B2C;
    end;
    // Верхний элемент A -> C
    W[ic].Add(W[ia].Items[W[ia].Count-1]);
    W[ia].Delete(W[ia].Count-1);
  end;
  // Система нормализована.
  // Теперь во всех башнях элементы отсортированы по убыванию.
  // Закончим классический алгноритм.
  while(W[ic].Count>0) do
  begin
    B2C;
  end;
  // Теперь в B всё отсортировано.
  // Заберём результат.
  for i := Low(A) to High(A) do
    A[High(A)-i+Low(A)] := W[ib].Items[i];
end;

Сложность: