0

Using the sorted built-in function without providing any optional arguments, how does python sort a list of dictionaries?

infrared
  • 3,566
  • 2
  • 25
  • 37
  • 3
    See http://stackoverflow.com/questions/3484293/is-there-a-description-of-how-cmp-works-for-dict-objects-in-python-2 – Mark Ransom Apr 12 '13 at 15:26

2 Answers2

8

Python 2 does attempt to provide an ordering (it does so for all types), first based on length (shorted dicts first), if the lengths are equal then by keys (a smaller key goes first), then if all keys are equal then on values (smaller values go first); see the characterize and dict_compare functions in the dictobject.c source code.

Short demo:

>>> sorted([{1:2}, {}])
[{}, {1: 2}]
>>> sorted([{1:2}, {0:1}])
[{0: 1}, {1: 2}]
>>> sorted([{1:2}, {1:1}])
[{1: 1}, {1: 2}]

In Python 3, it doesn't sort them at all; sorting dicts really makes no sense:

>>> sorted([{}, {}])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: dict() < dict()

See the Ordering Comparisons section of the What's New in Python 3 document.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • How can keys be equal in a `dict`? If by equal you mean of different `type` then I guess it compares type of keys instead if their values. So, `int` is smaller than `str` and `str` is smaller than `tuple`. – Ashwini Chaudhary Apr 12 '13 at 15:42
  • @AshwiniChaudhary: `unicode` keys are equal to `str` keys if they have the same ascii value. `int` keys can never be equal to `str` keys, but they *can* be equal to `float` keys. But you can define a dict with the same keys (all keys equal), so then values are compared. – Martijn Pieters Apr 12 '13 at 15:43
  • Ah! my bad, for a moment I thought we're sorting a single dict rather than sorting a list of dicts. – Ashwini Chaudhary Apr 12 '13 at 16:04
1

It doesn't (at least for python3):

>>> x = [{4:1}, {3:2}, {1:2}, {5:6}]
>>> x
[{4: 1}, {3: 2}, {1: 2}, {5: 6}]
>>> sorted(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: dict() < dict()

There isn't a reasonable default for specifying an ordering of dicts, so dicts are unorderable.

This behaviour has changed from python2, because comparisions have been reworked in python3. Before it was possible to compare almost anything using cmp(), which reflects in the ordering of lists. python3 fixes this, cmp() doesn't exist and comparisions are done using rich comparision methods, wich make only things comparable that really are, or how much sense does something like cmp(Exception(), 42) make?

mata
  • 67,110
  • 10
  • 163
  • 162