Сортировка Таноса :: Thanos sort

Разновидность вёдерной сортировки.
Алгоритм
В подмассиве (на первом шаге подмассивом является весь массив) вычисляется среднее арифметическое среди элементов. Затем элементы подмассива сравниваются со средним арифметическим и в зависимости от сравнения отправляются в левую или в правую часть подмассива.
Затем те же действия рекурсивно производятся по отдельности с левой и с правой частью подмассива.
Название
Шуточное название «сортировка Таноса» связано с тем, что если изначально элементы в массиве расположены рандомно, то итог сравнения со средним арифметическим (в результате чего элемент отправляется или влево или вправо) - случайное событие, почти как при щелчке Перчаткой Бесконечности.
Более научно называть алгоритм «средне-арифметическая вёдерная сортировка», так как такое наименование точно указывает на методы этой сортировки.
Программист Андрей Данилин (чья визуализация алгоритма взята за основу) использует название «русская сортировка половинами».
Характеристики алгоритма
Название | Сортировка Таноса (Thanos sort) | |
---|---|---|
Другие названия | Средне-арифметическая вёдерная сортировка (Average bucket sort), Русская сортировка половинами (Russian sorting halves) | |
Автор идеи | Андрей Данилин | |
Класс | Сортировки распределением | |
Устойчивость | Да | |
Сравнения | Да | |
Сложность по времени | Худшая | O(n2) |
Средняя | O(n + k) | |
Лучшая | O(n) | |
Сложность по памяти | Худшая | O(n × k) |