234
правки
Изменения
Нет описания правки
Обычно таким признаком служит лексикографический номер.
Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке, нежели чем в массиве, сортировка слиянием потребует $O(n^2)$ времени и $O(1)$ памяти против $O(n \log n)$ и $O(n)$с использованием массива; а вот сортировка пузырьком не изменится.
Также есть алгоритмы параллельной сортировки данных (т.н. [[Сортирующие сети]]), время работу которых $O(\log n)$.
|Да
|$O(n \log \log n)$
|Упоротая Очень сложная сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона.
|}
