3.4.3. Сортировка Боуза - Нельсона

Главным минусом предыдущих методов является удвоение размера памяти, первоначально занятой сортируемыми данными. Алгоритм Боуза – Нельсона является рекурсивным и не требует дополнительной памяти, т.е. упорядочение выполняется на месте исходного массива. Он основан на простой идее: слить две равные по размеру упорядоченные части можно слиянием их начальных, конечных половин, а также слиянием середин (2-й половины 1-го результата с 1-й половиной 2-го результата). Эта процедура иллюстрируется рисунком.

Если части не равны или не делятся точно пополам, процедуру уточняют соответствующим образом. Аналогично слияние «половинок» можно свести к слиянию «четвертушек», «восьмушек» и т. д. Таким образом, становится очевидной необходимость использования рекурсии.

Рисунок. Иллюстрация слияния частей двух серий

Обозначим r - расстояние между началами сливаемых частей, m - их размер и j - наименьший номер элемента. Будем считать, что выполняется сортировка по возрастанию.

Рекурсивный алгоритм сортировки Боуза- Нельсона

1. Слияние

   1. Начало рекурсии. Если j+r ≤ n, то

      1. Если m = 1, то

1. Если A[j] > A[j+r], то

Поменять местами A[i] и A[j+r].

2. Иначе

   1. m = m / 2.

   2. Выполнить Слияние «начал» от j до m с расстоянием r.

   3. Если j+r+m ≤ n, то

Выполнить Слияние «концов» от j+m до m с расстоянием r.

4. Выполнить Слияние «центральной части» от j+m до m с расстоянием m - r.

2. Основная часть рекурсии

   1. m = 1.

   2. Повторять

   3. Цикл слияния списков равного размера

      1. j = 1.

      2. Пока j+m ≤n

1) Выполнить Слияние (j,m,m);

2) j = j + 2m

2.3.3. Удвоение размера списка перед началом нового прохода

m = 2m.

Конец цикла 2.2, реализующего все слияния

Пока m < n.

Число сравнений и пересылок при реализации сортировки методом Боуза - Нельсона в самом худшем случае пропорционально n log n, т.е. сложность алгоритма O(n log n). Дополнительная память, как уже отмечалось, не требуется.

25