Аналіз сортування

C_min= 2(n-1) M_min=0

C_ср =1/2(n²+n-2)  M_ср= 1/4(n²+9n-10)

C_max =(n²+n)–1  M_max= 1/2(n²+3n-4)

Для даного методу найкращим є випадок, коли елементи із самого початку вже упорядковані, а найгірший - якщо елементи розташовані в  зворотному порядку.

Алгоритм простими включеннями можна легко поліпшити, користуючись тим, що готова послідовність a₁,..., a_i-1, у яку потрібно включити новий елемент, вже упорядкована. Тому місце включення можна знайти швидким бінарним методом.

procedure binaryinsertion (var a: massiv);

var

i,j,l,r,m: integer;

x: integer;

n1,n: integer;

begin

n1:= low(a);

n:= high(a);

for i:= k+1 to n do

begin

x:=a[i];

  l:=k;

  r:=i-1;

while (l<=r) do

  begin

  m:=(l+r) div 2;

  if x<a[m] then r:=m-1 else l:=m+1;

end;

for j:=i-1 downto  l do a[j+1]:=a[j];

a[l]:=x;

end;

end

Аналіз: кількість порівнянь C стає порядку n log n. Однак, це поліпшення не є вирішальним. Більш важливий показник М залишається порядку n².

Важлива властивість сортування включеннями: метод є стійким, тобто він залишає незмінним порядок елементів з однаковими ключами.