бинарный метод

Ответ от Наталья[гуру]
Метод бинарного включения (бинарные вставки)
Этот метод упоминается Джоном Мочли в 1646г. в первой публикации по машинной сортировке.
Данный метод является улучшенной версией метода простых вставок. Он основывается на том факте, что мы вначале ищем место куда нужно вставить элемент, а затем уже вставляем. Это дает существенный выигрыш по числу сравнений, но число перестановок по прежнему остается большим.
Поскольку все методы массива перед записью R[j] уже упорядочены, то можно использовать более эффективный метод поиска места куда надо вставить R[j]. В данном случае это алгоритм бинарного поиска. Например, если вставляется 64-я запись, то можно сравнить ее с 32-й, и если 64-я запись окажется меньше, то сравнить ее уже с 16-й, а если окажется больше, то сравнить с 48-й и т. д. Таким образом, место 64-й записи будет определено в худшем случае за шесть сравнений.
Общее число сравнений равно приблизительно N*logN, число перестановок попржнему остается квадратичнозависимым от N.