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