Novice - 1 year ago 81

Python Question

I was wondering what is the time complexity of sorting a dictionary by key and sorting a dictionary by value.

for e.g :

`for key in sorted(my_dict, key = my_dict.get):`

<some-code>

in the above line , what is the time complexity of

and is the time complexity of sorting by value and sorting by key are different ? Since , accessing the value by its key takes only O(1) time, both should be same ?

Thanks.

Answer Source

`sorted`

doesn't really sort a dictionary; it collects the iterable it receives into a list and sorts the list using the Timsort algorithm. Timsort is decidedly *not* a variant of quicksort, it is a hybrid algorithm closer to merge sort. According to wikipedia, its complexity is O(n log n) in the worst case, with optimizations to speed up the commonly encountered partially ordered data sets.

Since collecting the dict keys and values are both O(n), the complexity of both sorts is the same, determined by the sort algorithm as O(n log n).