Библиотечная сортировка :: Library Sort

Алгоритм

0. Создаём вспомогательный массив, в несколько раз больший чем основной.
1. Первый элемент переносим в середину вспомогательного массива.
2. Для очередного элемента методом бинарного поиска ищем место вставки во вспомогательном массиве.
- 2.1. Если нашли место для вставки, то переносим элемент и возвращаемся в пункт 2.
- 2.2. Если места для вставки не нашлось, производим перебалансировку вспомогательного массива и возвращаемся в пункт 2.
3. После обработки всех элементов переносим их обратно в основной массив.

Название (рус.)	Библиотечная сортировка, Сортировка библиотекаря
Название (англ.)	Library sort
Авторы	Майкл Бендер (Michael A. Bender), Мартин Фарах-Колтон (Martín Farach-Colton), Мигель Мостейро (Miguel Mosteiro)
Год	2004
Класс	Сортировки вставками
Сравнения	Есть
Временна́я сложность	лучшая	O(n)
	средняя	O(n log n)
	худшая	O(n²)
Сложность по дополнительной памяти	O(n)