Битоническая Сортировка (Bitonic Sort)

Битоническая Сортировка (Bitonic Sort) — это алгоритм сортировки, который использует концепцию битонических последовательностей (работает только для массивов, длинна которых является степенью двойки) для упорядочивания данных. Он особенно эффективен для параллельной обработки и часто применяется в архитектурах, поддерживающих параллелизм, таких как векторные процессоры и графические процессоры (GPU).

▎Принцип работы

1. Разделение: Исходный массив делится на две половины. Первая половина сортируется в возрастающем порядке, а вторая — в убывающем.

2. Объединение: После сортировки двух половин они объединяются в одну битоническую последовательность с помощью функции bitonic_merge.

3. Рекурсия: Шаги 1 и 2 повторяются рекурсивно для каждой половины до тех пор, пока не будет достигнут базовый случай (массив из одного элемента).

▎Временная сложность

• Временная сложность Bitonic Sort составляет O(log² n). Это связано с тем, что каждый уровень рекурсии требует O(n) операций для объединения битонических последовательностей, а количество уровней рекурсии составляет O(log n).

▎Пространсвенная сложность

• Пространственная сложность составляет O(n), так как требуется место для хранения временных массивов при объединении.

▎Устойчивость:

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

Реализация алгоритма на C++:

Реализация алгоритма на Python: