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

Сортировка Таноса

Разновидность вёдерной сортировки.

Алгоритм

В подмассиве (на первом шаге подмассивом является весь массив) вычисляется среднее арифметическое среди элементов. Затем элементы подмассива сравниваются со средним арифметическим и в зависимости от сравнения отправляются в левую или в правую часть подмассива.

Затем те же действия рекурсивно производятся по отдельности с левой и с правой частью подмассива.

Название

Шуточное название «сортировка Таноса» связано с тем, что если изначально элементы в массиве расположены рандомно, то итог сравнения со средним арифметическим (в результате чего элемент отправляется или влево или вправо) - случайное событие, почти как при щелчке Перчаткой Бесконечности.

Более научно называть алгоритм «средне-арифметическая вёдерная сортировка», так как такое наименование точно указывает на методы этой сортировки.

Программист Андрей Данилин (чья визуализация алгоритма взята за основу) использует название «русская сортировка половинами».

Характеристики алгоритма

НазваниеСортировка Таноса (Thanos sort)
Другие названияСредне-арифметическая вёдерная сортировка (Average bucket sort), Русская сортировка половинами (Russian sorting halves)
КлассСортировки распределением
УстойчивостьДа
СравненияДа
Сложность по времениХудшаяO(n2)
СредняяO(n + k)
ЛучшаяO(n)
Сложность по памятиХудшаяO(n × k)

Ссылки

Русская сортировка половинами

Блочная сортировка

Bucket sort