| Алгоритм | Временная сложность | Пространственная сложность | ||
|---|---|---|---|---|
| Низкая | Средняя | Высокая | Высокая | |
| Быстрая сортировка | O(nlog(n)) | O(nlog(n)) | O(n^2) | O(log(n)) |
| Сортировка слиянием | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(n) |
| Timsort | O(n) | O(nlog(n)) | O(nlog(n)) | O(1) |
| Пирамидальная сортировка | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(1) |
| Сортировка пузыркем | O(n) | O(n^2) | O(n^2) | O(1) |
| Сортировка вставками | O(n) | O(n^2) | O(n^2) | O(1) |
| Сортировка выбором | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Сортировка деревом | O(nlog(n)) | O(nlog(n)) | O(n^2) | O(n) |
| Сортировка Шелла | O(nlog(n)) | O(nlog(n)^2) | O(nlog(n)^2) | O(1) |
| Блочная сортировка | O(n+k) | O(n+k) | O(n^2) | O(n) |
| Поразрядная сортировка | O(nk) | O(nk) | O(nk) | O(n+k) |
| Сортировка подсчетом | O(n+k) | O(n+k) | O(n+k) | O(k) |
| Cubesort | O(n) | O(nlog(n)) | O(nlog(n)) | O(n) |