Какова пространственная сложность сортировки Python?

Сложность пространства определяется тем, сколько дополнительного пространства требуется алгоритму с точки зрения N элементов. И хотя, согласно документам, метод sort сортирует list на месте, он занимает некоторое дополнительное пространство, как указано в описании реализации:

Для timsort может потребоваться временный массив, содержащий до N//2 указателей, что означает до 2*N дополнительных байтов в 32-битных блоках. Можно ожидать, что такой большой временный массив потребуется при сортировке случайных данных; для данных со значительной структурой это может обойтись без использования дополнительной памяти кучи.

Следовательно, в худшем случае пространственная сложность равна O(N), а в лучшем случае O(1).

Встроенный в Python метод сортировки является ответвлением сортировки слиянием под названием Timsort, дополнительная информация здесь — https://en.wikipedia.org/wiki/Timsort.

По сути, она не лучше и не хуже, чем сортировка слиянием, а это означает, что ее время выполнения в среднем составляет O(n log n), а пространственная сложность — Ω(n).