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