Временная и пространственная сложность популярных алгоритмов сортировки:

1. Сортировка выбором
* Время: Лучшее Ω(n²) | Среднее Θ(n²) | Худшее O(n²)
* Память: O(1)

2. Сортировка вставками
* Время: Лучшее Ω(n) | Среднее Θ(n²) | Худшее O(n²)
* Память: O(1)

3. Сортировка пузырьком
* Время: Лучшее Ω(n) | Среднее Θ(n²) | Худшее O(n²)
* Память: O(1)

4. Сортировка Шелла
* Время: Лучшее Ω(n log n) | Среднее Θ(n log² n) | Худшее O(n²)
* Память: O(1)

5. Сортировка слиянием
* Время: Лучшее Ω(n log n) | Среднее Θ(n log n) | Худшее O(n log n)
* Память: O(n)

6. Быстрая сортировка
* Время: Лучшее Ω(n log n) | Среднее Θ(n log n) | Худшее O(n²)
* Память: O(log n)

7. Пирамидальная сортировка
* Время: Лучшее Ω(n log n) | Среднее Θ(n log n) | Худшее O(n log n)
* Память: O(1)

8. Поразрядная сортировка подсчётом
* Время: Лучшее Ω(n+k) | Среднее Θ(n+k) | Худшее O(n+k)
* Память: O(k)

9. Сортировка распределением (корзинная)
* Время: Лучшее Ω(n+k) | Среднее Θ(n+k) | Худшее O(n²)
* Память: O(n)

10. Поразрядная сортировка
* Время: Лучшее Ω(nk) | Среднее Θ(nk) | Худшее O(nk)
* Память: O(n+k)

Примечание: n = количество элементов, k = диапазон элементов