Вялая сортировка :: Slow Sort

Вялая сортировка

Алгоритм

  1. Если массив состоит из одного элемента, то завершаем рекурсию.
  2. Если массив состоит из двух и более элементов, то делим его пополам.
  3. Применяем рекурсивно алгоритм к левой половине.
  4. Применяем рекурсивно алгоритм к правой половине.
  5. Сравниваются элементы на концах массива (и меняются при необходимости).
  6. Рекурсивно применяем алгоритм к подмассиву без последнего элемента.

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

НазваниеВялая сортировка (Slow sort)
АвторЭндрю Броудер, Джордж Столфи
Год1986
КлассСортировки обменами
УстойчивостьУстойчивая
СравненияДа
Сложность по времениХудшаяΩ(n(log 2 n) / (2 + ε))
Средняя
Лучшая
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

Ссылки

Сортировки обменами

Slow sort