Сортировка деревом

Будем вставлять элементы в двоичное дерево. Для получения результата достаточно будет обойти получившееся дерево в глубину.

Код на Delphi:

type
  TAI = array of integer;

  TNode = class
            private
              Fkey : integer; // Собственный ключ узла
              FLeft, FRight: TNode; // Правое и левое поддеревья.
            public
              property Key: integer read FKey write FKey;

              constructor Create(aKey: Integer);
              procedure Insert(aNode: TNode); // Добавление узла в дерево
              procedure Extract(var A: TAI); // Извлечение дерева обратно в массив.
              destructor Destroy;override;
          end;
...

{ TNode }

constructor TNode.Create(aKey: Integer);
begin
  FKey := akey;
end;

destructor TNode.Destroy;
begin
  FLeft.Free;
  FRight.Free;
  inherited;
end;

procedure TNode.Extract(var A: TAI);
begin
  // Сначала извлекаем левое поддерево,
  if Assigned(FLeft) then FLeft.Extract(A);
  // потом свой ключ,
  SetLength(A, Length(A) +1);
  A[Length(A)-1] := FKey;
  // и правое поддерево.
  if Assigned(FRight) then FRight.Extract(A);
end;

procedure TNode.Insert(aNode: TNode);
begin
  if aNode.Key < Key then
  begin // Меньшие ключи добавляем в левое поддерево,
    if Assigned(FLeft) then FLeft.Insert(aNode)
                       else FLeft := aNode;
  end
    else
  begin // остальные - в правое.
    if Assigned(FRight) then FRight.Insert(aNode)
                        else FRight := aNode;
  end;
end;

...

procedure BTreeSort(var A: TAI);
var
    Tree: TNode;
    i:integer;
begin
  if length(A)>1 then
  begin
    // Начинаем дерево первым элементом
    Tree := TNode.Create(A[Low(A)]);
    // и вставляем в него все остальные.
    for i := Low(A)+1 to High(A) do
    begin
      Tree.Insert(TNode.Create(A[i]));
    end;
    // Дерево сформировано. Сбрасываем массив.
    Setlength(A,0);
    // Извлекаем результат обратно в массив.
    Tree.Extract(A);
    // Освобождаем память из под дерева.
    Tree.Free;
  end;
end;

Сложность: