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

Сложность сортировки списка зависит от алгоритма.

O(n log n) — оптимальная сложность для сравнения (например, sorted() в Python использует TimSort).
O(n²) — для простых алгоритмов (пузырьковая, вставками).
O(n) — для не сравнения (например, подсчётом, но требует доп. условий).

Пример:

import timeit

lst = [5, 2, 9, 1, 5, 6]
print(timeit.timeit(lambda: sorted(lst), number=10000))  # O(n log n)