Словесное описание алгоритма. 0. В готовую подпоследовательность записывается a1, во вход-ную - a2, , an

0. В готовую подпоследовательность записывается a₁, во вход-ную - a₂,…, a_n.

1. i:=2.

2. Переносим элемент x = a_i из входной подпоследовательности в готовую так, чтобы готовая подпоследовательность осталась отсортированной. Для этого:

а) расширяем готовую подпоследовательность слева с помощью барьера a ₀ = x.

б) параметр цикла поиска подходящего места принимает значение j:=i-1;

в) пока x<a_j, выполняется сдвиг элемента a_j вправо (a_j+1:= a_j) и уменьшение j на единицу (j:= j -1);

г) a_j+1:= x.

3. i: =i +1. Если i≤n, то переходим на п. 2, иначе сортировка закончена.

Алгоритм сортировки простыми включениями легко можно улучшить, пользуясь тем, что готовая подпоследовательность a₁,…, a_i+1, в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее. Очевидно, что здесь можно применить бинарный поиск, который исследует средний элемент готовой подпоследовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

Таблица 1.1