# Sorting ordered dicts

**URL:** <https://discuss.python.org/t/sorting-ordered-dicts/25336>\
**Category:** Ideas\
**Created:** [March 31, 2023, 2:16pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336 "2023-03-31T14:16:57Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [March 31, 2023, 2:16pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/1 "2023-03-31T14:16:57Z")

</div>

I think it would be good to add a way of sorting OrderedDicts.

I read [this topic](https://discuss.python.org/t/add-a-dict-sort-method/5747) which sought to add the .sort() method to builtin dicts. I don’t think it fits in with the “spirit” of the builtin dict, whose ordering is only a sidenote. And there are apparently numerous implementation and performance issues.

However, these objections don’t apply to collections.OrderedDict, whose ordering aspect comes first, if we believe its doc section. I think it makes sense to add a .sort method which would reorder the entries in-place, which has similarities with what `move_to_end` does. If a sorting algorithm can fit well with the double-linked list format (I think) OrderedDict uses, that could even be a performance improvement over the existing way, `OrderedDict(sorted(od.items()))`.

---

<div class="post-metadata">

**Author:** ![bverheg](https://avatars.discourse-cdn.com/v4/letter/b/cc9497/32.png) [@bverheg](https://discuss.python.org/u/bverheg)\
**Post date:** [March 31, 2023, 7:48pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/2 "2023-03-31T19:48:38Z")

</div>

dict keys can be of any hashable type and are not always sortable. How would one sort a dict like {0:1, ‘a’:2, int:3} ? If the keys are sortable, you can just create a new sorted dict with a comprehension:

```auto
sorted_d = {key:d[key] for key in sorted(d.keys())}

```

---

<div class="post-metadata">

**Author:** ![chepner](https://avatars.discourse-cdn.com/v4/letter/c/22d042/32.png) [@chepner](https://discuss.python.org/u/chepner)\
**Post date:** [March 31, 2023, 8:50pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/3 "2023-03-31T20:50:21Z")

</div>

By that argument, `list` should not have a `sort` method either.

```auto
>>> x = [0, 'a', int]
>>> x.sort()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'str' and 'int'

```

That just means you would need an appropriate `key` function to say how to compare two otherwise non-comparable values, not that the idea of sorting doesn’t apply.

Hypothetically,

```
d = OrderedDict{0:1, 'a': 2, int: 3)
d.sort(key=some_appropriate_function)

```

---

<div class="post-metadata">

**Author:** ![Quercus](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/quercus/32/31483_2.png) [@Quercus](https://discuss.python.org/u/Quercus)\
**Post date:** [March 31, 2023, 9:10pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/4 "2023-03-31T21:10:42Z")

</div>

> [@chepner](#):
>
> That just means you would need an appropriate `key` function …

Yes, with a good `key` function we can do wonders.

```auto
x = [0, 'a', int, 9, 3, True]
x.sort(key=lambda thing: str(thing))
print(x)

```

Output:

```
[0, 3, 9, <class 'int'>, True, 'a']

```

So, if we were to define a means of sorting an `OrderedDict`, we’d just need to be able to supply a good `key` function that would work for every item. An issue would be what should happen if the `key` function couldn’t do the job.

from the Zen:

```
Errors should never pass silently.

```

So it might be best to raise an exception in that situation.

If no `key` function is given, then we would either need a default action, or to raise an exception. What do you all feel would be best for that occasion?

---

<div class="post-metadata">

**Author:** ![Rosuav](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rosuav/32/3429_2.png) [@Rosuav](https://discuss.python.org/u/Rosuav)\
**Post date:** [March 31, 2023, 9:32pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/5 "2023-03-31T21:32:53Z")

</div>

> [@Quercus](#):
>
> If no `key` function is given, then we would either need a default action, or to raise an exception. What do you all feel would be best for that occasion?

I would expect the exact same behaviour that `sorted()` and `list.sort()` use.

But OrderedDict can be sorted with the comprehension as given above, and I’m really not sure of the use-cases for this, so I’m dubious that a new method is needed.

---

<div class="post-metadata">

**Author:** ![NeilGirdhar](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/neilgirdhar/32/5776_2.png) [@NeilGirdhar](https://discuss.python.org/u/NeilGirdhar)\
**Post date:** [March 31, 2023, 10:35pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/6 "2023-03-31T22:35:02Z")

</div>

Can you come up with an algorithm that would benefit from the method? Because it seems to me that you actually need a different data structure, e.g., [sorted containers](https://github.com/grantjenks/python-sortedcontainers/).

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [March 31, 2023, 11:40pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/7 "2023-03-31T23:40:44Z")

</div>

As a recent example, I have a list of entities which the player has affinities with (it’s in a game context), and I have a mapping storing the affinity for each entity.  
In my case I frequently have to show the entities sorted by value, I’m currently using `sorted(dic, key=dic.get)` to get a list of those but then I lose the easy access to the affinity values from the sorted list of keys.  
When I show it in a menu where you can manually change the value for each key, it would help UX that the items don’t change ordering as a result of these increases, and stay the same until you close the menu - so if I were using sorted containers, which seem like a great thing I could use in other contexts, I would have to copy the keys in a fixed-order list each time otherwise they would bump one another around when their values change.  
In my use case it would then be easiest to sort the dict when the menu is opened, or when it is similarly accessed.

Also, this is purely speculation on my part since I don’t know much about sorting algorithms and container performance in Python, but maybe there could be a (considerable ?) performance improvement in OrderedDict when using an in-place sorting rather than generating the items, making a list out of them, sorting that list, and going through the entire double-linked list generation from the beginning each time you want to sort it using the snippet I used or @bverheg’s.

Otherwise yes, the error handling mechanism would be the exact same one as for the list sorting API, the default sort would be by keys kecause then it’s dead easy to sort by value using d.get as the key function, and only slightly more complex to sort by items using a `lambda k:(k, d[k])`.

---

<div class="post-metadata">

**Author:** ![NeilGirdhar](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/neilgirdhar/32/5776_2.png) [@NeilGirdhar](https://discuss.python.org/u/NeilGirdhar)\
**Post date:** [April 1, 2023, 12:33am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/8 "2023-04-01T00:33:49Z")

</div>

If you want to optimize for computational complexity, then I think you could use different data structures.

Keep the mapping: M from entity to value.  
Add a separate list L of entities displayed.

Modification of entity value is O(1), opening the display list is O(nlogn) to copy from M to L and sort.

Alternatively, make M a sorteddict and keep L for display.  
Modification of an entity value is O(logn), opening the display list is O(n) to copy from M to L.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 1, 2023, 6:33am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/9 "2023-04-01T06:33:38Z")

</div>

> [@Gouvernathor](#):
>
> If a sorting algorithm can fit well with the double-linked list format (I think) OrderedDict uses, that could even be a performance improvement over the existing way, `OrderedDict(sorted(od.items()))`.

Could you tell me the name of the algorithm for sorting doubly-linked list faster than creating temporal list?  
Can the algorithm support `key` function efficiently? Or should the OrderedDict.sort() function use `cmp` function?

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 1, 2023, 12:05pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/10 "2023-04-01T12:05:44Z")

</div>

> [@NeilGirdhar](#):
>
> Keep the mapping: M from entity to value.  
> Add a separate list L of entities displayed.

In that case I still end up with data redundency, since adding or removing an entity to the dict doesn’t reflect on the list and vice versa, an issue I’m currently having which forces me to keep the list relatively short-lived and have to manage different containers holding similar data at the same time.

Also, but this enters speculations on my part, the first example sorts the same unordered list each time (with sometimes elements getting added or removed). I think there are sorting algorithms which waste very little time when the data is already mostly sorted. With an inplace sort, there could be considerably less loss of time if I show the menu twice and only one or two values changed and need to be reordered within a mostly sorted dict.

> [@methane](#):
>
> Could you tell me the name of the algorithm for sorting doubly-linked list faster than creating temporal list?

Read again, I said _if_ a sorting algorithm can fit well with it. I have no idea whether or not this is the case, my point is, OrderedDict and dict are not implemented the same way so something inefficient on the one may be better on the other.  
Also why not creating a temporary list ? Can’t you create one, and reattribute the begin and end pointers to the secondary list when the sorting is done ?

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 1, 2023, 1:35pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/11 "2023-04-01T13:35:32Z")

</div>

> [@Gouvernathor](#):
>
> Also why not creating a temporary list ? Can’t you create one, and reattribute the begin and end pointers to the secondary list when the sorting is done ?

I just wanted to confirm what “in-place” and “sorting algorithm can fit well with the double-linked list” in your first post mean.  
I thought that you assumed sorting double-linked list in-place. But I was wrong.

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 1, 2023, 2:20pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/12 "2023-04-01T14:20:08Z")

</div>

I mean in-place as : the dict (or ordereddict) object stays the same, it’s mutated instead of another instance being created and put in the same variable - as you currently have to if you want a sorted dict.  
That does not mean you can’t create a temporary _linked list_ inside the dict instance to do the sorting behind the scenes. I don’t really care if we do that or not, it’s not part of the public API anyway, so whatever favors performance is fine.

---

<div class="post-metadata">

**Author:** ![storchaka](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/storchaka/32/217_2.png) [@storchaka](https://discuss.python.org/u/storchaka)\
**Post date:** [April 1, 2023, 3:12pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/13 "2023-04-01T15:12:32Z")

</div>

Something like this?

```auto
for key in sorted(od):
    od.move_to_end(key)

```

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 1, 2023, 3:29pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/14 "2023-04-01T15:29:44Z")

</div>

That would be one good way to do it, yes. But a method accessing the links themselves would be more performant : for example instead of setting the end pointer n times, it would do so one time.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 1, 2023, 3:45pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/15 "2023-04-01T15:45:40Z")

</div>

> [@Gouvernathor](#):
>
> In my case I frequently have to show the entities sorted by value, I’m currently using `sorted(dic, key=dic.get)` to get a list of those but then I lose the easy access to the affinity values from the sorted list of keys.

I think this is the best approach. OrderedDict.sort() wouldn’t faster than it. And OrderedDict is memory inefficient.

You don’t lose easy access to the values. You can get it by `dic[key]`. It’s easy enough.

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 2, 2023, 5:02am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/16 "2023-04-02T05:02:30Z")

</div>

Accessing the sorted values is not : you have to iterate through the sorted list of keys, and index the dict for each one. Compared to being able to sort the dict, it’s about the same inefficiency as doing

```py
for i in range(len(l)):
    l[i]

```

instead of just iterating the list.  
Not to mention my previous point about sorting methods that are faster on already sorted data, which may exist and be useful when sorting the dict in-place but can’t when sorting a copy of the keys.  
That and the link being lost if you add/remove a key.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 2, 2023, 5:32am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/17 "2023-04-02T05:32:31Z")

</div>

> [@Gouvernathor](#):
>
> Accessing the sorted values is not : you have to iterate through the sorted list of keys, and index the dict for each one.

This overhead would be much smaller than OrderedDict.sort().  
If you need to iterate value very frequently, you can `sorted(dic.items(), key=itemgetter(1))` instead.

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 2, 2023, 1:58pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/18 "2023-04-02T13:58:24Z")

</div>

> [@methane](#):
>
> If you need to iterate value very frequently, you can `sorted(dic.items(), key=itemgetter(1))` instead.

No, that’s the opposite : yours is a list of the keys ordered by values, whereas I was talking about iterating the values ordered by keys.  
How would sorting something from scratch repetitively instead of tweaking mostly-sorted data, and manipulating two containers instead of one, add less overhead than in-place sorting ? That doesn’t make sense.

---

<div class="post-metadata">

**Author:** ![Rosuav](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rosuav/32/3429_2.png) [@Rosuav](https://discuss.python.org/u/Rosuav)\
**Post date:** [April 2, 2023, 2:41pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/19 "2023-04-02T14:41:12Z")

</div>

> [@Gouvernathor](#):
>
> How would sorting something from scratch repetitively instead of tweaking mostly-sorted data, and manipulating two containers instead of one, add less overhead than in-place sorting ? That doesn’t make sense.

You’d be amazed how efficient timsort is at tweaking mostly-sorted data. Given that a dictionary remembers insertion order, you could fairly easily re-sort and return to dict form, and then it’s mostly sorted for next time.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 2, 2023, 4:57pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/20 "2023-04-02T16:57:15Z")

</div>

> [@Gouvernathor](#):
>
> No, that’s the opposite : yours is a list of the keys ordered by values, whereas I was talking about iterating the values ordered by keys.

Then, `dict(sorted(dic.items(), key=itemgetter(1)))`.

> [@Gouvernathor](#):
>
> How would sorting something from scratch repetitively instead of tweaking mostly-sorted data, and manipulating two containers instead of one, add less overhead than in-place sorting ? That doesn’t make sense.

What you call “in-place” is not true “in-place”. It is out-of-place sort + updating linked list based on the sort result.  
Linked list is slow and memory inefficient. Dict is faster and more efficient because it is array-based.

If can not believe me, try implementing `OrderedDict.sort()`.

[Next page](https://discuss.python.org/t/sorting-ordered-dicts/25336.md?page=2)
