временная сложность сортировки словаря

Question

Мне было интересно, какая временная сложность сортировки словаря по ключевым словам и сортировка словаря по значению.

для например:

for key in sorted(my_dict, key = my_dict.get): 
    <some-code> 

в строке выше, что временная сложность отсортирован? Если предполагается, что используется quicksort, то это O (NlogN) в среднем и O (N * N) в худшем случае?

и сложна ли сортировка по значению и сортировка по ключевым словам различны? Так как доступ к значению по его ключу занимает только время O (1), оба должны быть одинаковыми?

Спасибо.

Answer 1

sorted действительно не сортирует словарь; он собирает итерируемый, который он получает в список, и сортирует список, используя Timsort algorithm. Timsort явно не вариант quicksort, это гибридный алгоритм, близкий к сортировке слияния. Согласно wikipedia, его сложность - O (n log n) в худшем случае, с оптимизацией для ускорения часто встречающихся частично упорядоченных наборов данных.

Поскольку сбор ключей ключей и значений O (n), сложность обоих видов одинакова, определяемая алгоритмом сортировки как O (n log n).