Изменения
Нет описания правки
Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
=== #Стабильность ===
''Стабильной сортировкой'' называется сортировка, не меняющая порядка объектов с одинаковыми ключами.
|$O(n \log n)$
|$O(n \log n)$
|$O(n)$ (обычная реализация)<br>$O(1\log n)$<br> ([[Cортировка слиянием с использованием O(1) дополнительной памяти|модифицированная реализация]])
|Да
|$O(n \log n)$
|[[Карманная сортировка|Карманная сортировка <br>(Bucked Sort)]]
|$O(n)$
|$O(n \log log_k n)$
|$O(n^2)$
|$O(n)$
|- align = "center"
|[[Цифровая сортировка|Цифровая сортировка <br>(Radix Sort)]]
|$O(n \log lg n)$|$O(n \log lg n)$|$O(n \log lg n)$
|$O(n)$
|Да
== Ссылки ==
[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8| Википедия срывает покровы]
</wikitex>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
