Сортировка прямым слиянием Боуза-Нельсона :: Bose-Nelson Merge Sort

Массив делится пополам - на левую и правую половины.
Элементы разбиваются на группы.
На первой итерации это двойки элементов (1-й элемент левой половины + 1-й элемент правой половины, 2-й элемент левой половины + 2-й элемент правой половины и т.д.), на второй итерации - четвёрки элементов (1-й и 2-й элементы левой половины + 1-й и 2-й элементы правой половины, 3-й и 4-й элементы левой половины + 3-й и 4-й элементы правой половины и т.д.), на третьей - восьмёрки и т.д.
Элементы каждой группы из левой половины являются отсортированным подмассивом, элементы каждой группы из правой половины также являются отсортированным подмассивом.
Производим слияние отсортированных подмассивов из предыдущего пункта.
Возвращаемся в пункт 1. Цикл продолжается до тех пор, пока размеры групп меньше размера массива.

Ссылки