time complexity of sorting a dictionary

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 sorted ? If it is assumed that quicksort is used, is it O(NlogN) on an average and O(N*N) in the worst case ?

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.

Python uses Timsort http://stackoverflow.com/questions/1517347/about-pythons-built-in-sort-method — Gennady Kandaurov, Nov 22 '16 at 20:38
They are not different , both of them are list with `N` members — ᴀʀᴍᴀɴ, Nov 22 '16 at 20:38
You can't sort a dictionary, you can only sort a sequence *returned* from a dictionary. If you try to iterate it directly, you get a sequence of the keys without the values. — Mark Ransom, Nov 22 '16 at 20:46

user4815162342 · Accepted Answer · 2016-11-22T20:52:08.053

15

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).

edited Nov 22 '16 at 20:52

answered Nov 22 '16 at 20:43

user4815162342

141,790
18
296
355

Did you mean O(n log n) at the end? – user2357112 Nov 22 '16 at 20:46

time complexity of sorting a dictionary

1 Answers1