Сортировка вставками с бинарным поиском

Усовершенствование сортировки простыми вставками, в которой для поиска места вставки используектся бинарный поиск.

type
  TAI = array of integer;
...
procedure InsertionWithBSearchSort(var A: TAI);
var
    i, j: integer;
    left, right, mid: integer;
    value: integer;
begin
  for i := Low(A)+1 to High(A) do
  begin
    left := Low(A);
    right := i;
    while left<right do
    begin
      mid := (left+right) div 2;
      if A[i]<A[mid] then right := mid
                     else left  := mid + 1;
    end;
    value := A[i];
    for j := i-1 downto left do
      A[j+1] := A[j];
    A[left] := value;
  end;
end;

 

Сложность:

Максимальная O(N(log(N))
Минимальная O(N(log(N))
Средняя O(N(log(N))