# Sorted data structure in the stdlib? **URL:** \ **Category:** Ideas\ **Created:** [July 2, 2026, 4:01pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994 "2026-07-02T16:01:51Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![irazza](https://avatars.discourse-cdn.com/v4/letter/i/ebca7d/32.png) [@irazza](https://discuss.python.org/u/irazza)\ **Post date:** [July 2, 2026, 4:01pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/1 "2026-07-02T16:01:51Z")
Hi, I find myself reaching for `sortedcontainers` pretty often, and it made me wonder why it isn’t in the stdlib. Looking at pypistats, it gets ~9.8M downloads/day (as of July 1), so I’m clearly not the only one using it 🙂 I think the backend ds for the implementation of SortedDict or Set are well known (B-trees, red-black trees, …). Do you think Python could adopt `SortedDict`/`SortedSet` into `collections` at this point? Anyone know if this has been proposed before? Thanks ---
**Author:** ![jsbueno](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/jsbueno/32/1210_2.png) [@jsbueno](https://discuss.python.org/u/jsbueno)\ **Post date:** [July 2, 2026, 4:43pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/2 "2026-07-02T16:43:14Z")
I believe some wouldn 't do bad - and up to Python 3.17, people could have fun reaching good enough designs, once several trade-offs are taken into account, to land into the stdlib. I believe the second step (the first is your very post), is getting more motivation into it: your post is nice, but can we get the idea even more compelling? Then, once we have a motivated mass of people willing to do it, we can bikeshed on which structures, and draft a pep. I remember in the old mailing list days proposing just a small class wrapper around the heapq functions (so, we’d get a sorted data-structure ready to use), and got hit by “not every small 10 liner need to become a stdlib class” reply that basically ended the thread there (even because I immediately agreed on it). Some 10 years later, though, lessons learned: it is not only just 10-extra lines: there is a lot of edge cases and extra functionality (make operators work, for example), that could go in a well crafted such wrapper-class around heapq.\* - what happens is that people just reach for the “raw” heapq functions which results in code that is longer, harder to read, and “stays in the path between the programmer and his idea” in a “less Pythonic way” than ideal. ---
**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:** [July 2, 2026, 5:10pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/3 "2026-07-02T17:10:36Z")
> [@irazza](#): > > Do you think Python could adopt `SortedDict`/`SortedSet` into `collections` at this point? What’s the advantage of having it in `collections` rather than fetching `sortedcontainers`? ---
**Author:** ![facundo](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/facundo/32/53_2.png) [@facundo](https://discuss.python.org/u/facundo)\ **Post date:** [July 2, 2026, 5:47pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/5 "2026-07-02T17:47:34Z")
Note that for simple cases we do have something in the stdlib: ```python >>> l = [] >>> for w in ["x", "foo", "yy", "foobar", ""]: ... bisect.insort(l, w, key=len) ... print(l) ... ['x'] ['x', 'foo'] ['x', 'yy', 'foo'] ['x', 'yy', 'foo', 'foobar'] ['', 'x', 'yy', 'foo', 'foobar'] >>> ``` ---
**Author:** ![Andrew5057](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/andrew5057/32/35016_2.png) [@Andrew5057](https://discuss.python.org/u/Andrew5057)\ **Post date:** [July 2, 2026, 5:56pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/6 "2026-07-02T17:56:23Z")
Depending on use case, there’s also [heapq](https://docs.python.org/3/library/heapq.html). ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [July 2, 2026, 6:40pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/7 "2026-07-02T18:40:51Z")
`sortedcontainers` is a marvel - generally better than anything that came before or after it. Its author gave a PyCon talk on it about a decade ago: [![](https://us1.discourse-cdn.com/flex002/uploads/python1/original/3X/7/a/7a0b635308aac7363bba7a075b8ee198dee61189.jpeg "Grant Jenks - Python Sorted Collections - PyCon 2016") ](https://www.youtube.com/watch?v=7z2Ki44Vs4E) Near the end, he expressed mixed feelings about folding it into the core. Yes, its absence is conspicuous _by_ its absence, but he was skeptical that key design decisions could survive the seemingly endless bikeshedding that comes with any public design debate. His own decisions were driven by extensive testing and benchmarking, nothing about fashion or social maneuvering. So it’s a kind of a poster child for a shift in core development: in the very early “batteries included” days, Guido woiuld have likely said “sure, fold it in!”. But now it’s an illustration of a repeated Catch-22: “Put irt on PyPI first” to demonstrate real demand. “Ah, it giot tremendous uptake on P:yPI - so no need to put into the core”. Grant (Jenks - the author) appears to have moved on to other things. So I expect not8ng will change,.While licensing allows for it, there is no precedent for putting something into the core without the author’s active cooperation The very capable and popular `regex` extension module is in a similar boat, but in that case I believe (but don’t know) that its author doesn’t want to be tied to CPython’s release cycle and pretty elaborate workflows. Grant _appears_ to be more put off by the low signal-to-noise ratio of the the public core design process. Possible example: a predecessor of `sortedcontainers` had its version of `sortedilst.pop()` remove the first element of a list. To Grant “it was obvious” that it _should_ remove the last element instead. So that’s what he did. In a public debate, it’s thoroughly predictable that someone would passionately argue to have two different methods to pick which, and someone else argue for an optional keyword argument to pick which. Some loon 😉 may then go to on to argue that a module-level flag should control the default, and then a thread-level default, and then a context manager ,..,. these things can go on for years, In the meantime, Grant applied his time instead to researching and achieving factor-of-10 speedups in plausible large workloads,.There’s an art to knowing when to say “good enough!” and move on, which comes hard to purists To my eyes, Grant was exceptionally skilled at that (for example, there are reasons to imagine that a Fenwick tree may do better than a “Jenks index” at speeding indexing by position, but best I know that wasn’t explored}, ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [July 2, 2026, 8:54pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/8 "2026-07-02T20:54:21Z")
> [@facundo](#): > > Note that for simple cases we do have something in the stdlib: > > ```python > >>> l = [] > >>> for w in ["x", "foo", "yy", "foobar", ""]: > ... bisect.insort(l, w, key=len) > ... print(l) > > ``` That’s what inspired `sortedcontainers`, in fact. Grant noticed that this very simple code ran much faster than eleaborte C-coded extension modules implementing assorted “asymptotically superior” tree structures. The constant factor of the O(n) dead-simple approach is so small (mostly thanks to modern CPUs being blazing fast at moving pointers in L1 cache) that the list generally has to grow to over a thousand elements before O(\log{n}) tree structures repay their higher fixed costs. Under the covers, a `sortedcontainers.SortedList` _is_ just a list of Python lists. The sublists are magically kept small enough so that native `bisect()` and `insort()` operations remain very fast. Each sublist changes length on its own as needed, rarely requriring splitting, or merging with adjacent lists, when a sublist grows “too large” or “too small”, The devil in the details, of course, ---
**Author:** ![irazza](https://avatars.discourse-cdn.com/v4/letter/i/ebca7d/32.png) [@irazza](https://discuss.python.org/u/irazza)\ **Post date:** [July 3, 2026, 6:55am UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/9 "2026-07-03T06:55:16Z")
Fair point! In my opinion it’s more about not needing an extra dependency for something this common, and having one implementation instead of everyone picking their library (in this case there are several high quality library with different backend structure). ---
**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:** [July 3, 2026, 6:57am UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/10 "2026-07-03T06:57:32Z")
> [@irazza](#): > > not needing an extra dependency for something this common, Everyone thinks that _their_ one dependency is extremely common. Got some stats on how common it is? > [@irazza](#): > > having one implementation instead of everyone picking their library (in this case there are several high quality library with different backend structure). Do they have different benefits? Is there advantage to be had from the distinction? ---
**Author:** ![irazza](https://avatars.discourse-cdn.com/v4/letter/i/ebca7d/32.png) [@irazza](https://discuss.python.org/u/irazza)\ **Post date:** [July 3, 2026, 7:27am UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/12 "2026-07-03T07:27:07Z")
> [@Rosuav](#): > > Everyone thinks that _their_ one dependency is extremely common. Got some stats on how common it is? Besides pypistats (~9 Million downloads/day), it’s used in projects like [Dask distributed](https://github.com/dask/distributed/blob/main/pyproject.toml), [Trio](https://github.com/python-trio/trio/blob/main/pyproject.toml) , and [Angr](https://github.com/angr/angr/blob/master/pyproject.toml) just to cite a few. It’s also packaged in [Debian](https://packages.debian.org/sid/python3-sortedcontainers) and [conda-forge](https://github.com/conda-forge/sortedcontainers-feedstock). > [@Rosuav](#): > > Do they have different benefits? Is there advantage to be had from the distinction? Actually, they do. `sortedcontainers` isn’t a tree, it’s a list-of-sublists by design, it is tuned for cache locality. B-tree/RB-tree implementations trade some of that for guaranteed O(log n) worst-case and less memory overhead per element. I would say that different workloads favor different backends. ---
**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:** [July 3, 2026, 7:54am UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/13 "2026-07-03T07:54:37Z")
> [@irazza](#): > > Actually, they do. `sortedcontainers` isn’t a tree, it’s a list-of-sublists by design, it is tuned for cache locality. B-tree/RB-tree implementations trade some of that for guaranteed O(log n) worst-case and less memory overhead per element. I would say that different workloads favor different backends. That’s a good reason NOT to have it in the stdlib then; if different workloads favour different modules, then it’s usually best that they all be on PyPI. (Unless there’s one very obvious default and the others are specialties or something.) ---
**Author:** ![irazza](https://avatars.discourse-cdn.com/v4/letter/i/ebca7d/32.png) [@irazza](https://discuss.python.org/u/irazza)\ **Post date:** [July 3, 2026, 8:20am UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/14 "2026-07-03T08:20:33Z")
> [@tim.one](#): > > The constant factor of the O(n) 𝑂(𝑛) dead-simple approach is so small (mostly thanks to modern CPUs being blazing fast at moving pointers in L1 cache) that the list generally has to grow to over a thousand elements before O(\log{n}) 𝑂(log⁡𝑛) tree structures repay their higher fixed costs. I see your point, but if the sorted-list-of-sublists design is this good, why hasn’t it shown up as standard approach in other languages? Rust chose a B-tree, C++ an RB-tree, I’m curious whether there’s something Python-specific making this approach shine, might it be interesting to try a C-extension B-tree implementation and benchmark it against `sortedcontainers` directly? ---
**Author:** ![irazza](https://avatars.discourse-cdn.com/v4/letter/i/ebca7d/32.png) [@irazza](https://discuss.python.org/u/irazza)\ **Post date:** [July 3, 2026, 8:32am UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/15 "2026-07-03T08:32:44Z")
Besides pypistats (~9 Million downloads/day), it’s used in projects like [Dask distributed](https://github.com/dask/distributed/blob/main/pyproject.toml), [Trio](https://github.com/python-trio/trio/blob/main/pyproject.toml) , and [Angr](https://github.com/angr/angr/blob/master/pyproject.toml) just to cite a few. It’s also packaged in [Debian](https://packages.debian.org/sid/python3-sortedcontainers) and [conda-forge](https://github.com/conda-forge/sortedcontainers-feedstock). From my point of view it can be useful a proof of concept as a C-extension implementing a sorted set for example. Do you have any other ideas? ---
**Author:** ![pf\_moore](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/pf_moore/32/35_2.png) [@pf\_moore](https://discuss.python.org/u/pf_moore)\ **Post date:** [July 3, 2026, 8:39am UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/16 "2026-07-03T08:39:58Z")
> [@irazza](#): > > Besides pypistats (~9 Million downloads/day), it’s used in projects like [Dask distributed](https://github.com/dask/distributed/blob/main/pyproject.toml), [Trio](https://github.com/python-trio/trio/blob/main/pyproject.toml) , and [Angr](https://github.com/angr/angr/blob/master/pyproject.toml) just to cite a few. It’s also packaged in [Debian](https://packages.debian.org/sid/python3-sortedcontainers) and [conda-forge](https://github.com/conda-forge/sortedcontainers-feedstock). That’s hardly a lot, compared to (say) requests, which is used far more often and is also not in the stdlib. And Debian and conda-forge package huge numbers of Python libraries, so they aren’t really good indicators of whether something is worth including in the stdlib (quite the opposite, actually - because it’s provided by common distributors, it’s easily obtainable and so there’s _less_ need for sortedcontainers to be in the stdlib). ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [July 3, 2026, 2:16pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/17 "2026-07-03T14:16:04Z")
My couple of cents is that it would make more sense to focus on more general “fast insertion/random access” data structure as opposed to “sorted container”. Once you have one, making sorted structure is as trivial as [SortedCollection « Python recipes « ActiveState Code](https://code.activestate.com/recipes/577197-sortedcollection/). If later we want full batteries for sorted container, optimized methods `obj.bisect_[left|right]` / `obj.insort_[left|right]` can be added later (fyi - these can also be made adaptive to similar degree that `TimSort` is). The point is that it will be very awkward having `SortedList`, but being unable to use underlying structure for anything else. * * * So if this is desirable, I would suggest a technical thread where people can share and compare different list implementations that fit this profile, such as `blist`, `sortedcontainers` approach, `tiered vector`, etc. I have done a fair bit of work on this exploration and would have some stuff to contribute to such thread, but haven’t yet arrived at something that I would be comfortable proposing to stdlib. Reason being is that, at least to me, implementing several of them is non-trivial effort and it is hard to commit until the landscape is fully explored and tested. * * * Also, note that implementing this in `C` is non-trivial endeavour and could be a large chunk of code and complexity - committing to something that proves sub-optimal later would be a big shame. While if one is ok with Python implementation - `sortedcontainers` is your answer. If it is unmaintained and you want maintained - you can fork and maintain. ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [July 3, 2026, 5:31pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/18 "2026-07-03T17:31:33Z")
Do read the extensive `sortedcontainrs` docs. Grant did _major_ testing against all available alternatives (including C extensions for B trees, AVL tress, red-black trees, …). `sortedlist` did as well as any, on speed and memory overhead, and better than most. It was a “category killer”, and especially effective under PyPy. The CPythion speed comes from that `bisect`already does search and “insort” on plain Python lists in efficient C Approaches to sorted dicts and sets are open to other tradeoffs. Grant’s version of a sorted dict uses a sortellist _and_ a Python dict under the covers, and his version of a sorted set similarly uses a sortellist _and_ a Python set under the covers. That’s not memory-efficient, but preserves expected O(1) lookup times. O(1) indexing by position isn’t as important for sorted lists. The code does special-case indices of 0 and -1 (actually a bit more general than just that) so that uses as a priority queue (single or double ended!) do lookups in O(1) time. Grant also rented time on “giant machines” to test performance at scale on containers with dozens of billions of elements. The results are also written up in the docs. They did very well too, but for “very large” containers it can pay to increase the default “load factor”.. Most applications won’t care. For very, very large containers, the two-level structure of `sortlist` can become a hard bottleneck. It’s basically a very shallow but very broad B+-tree structure. In return for not scaling well “in theory” to unbounded sizes, practical sizes benefit from simpler (and faster) code. Its attention to pragmatics is also impressive. For example, it’s apparently faster than anything else at initializing a large sorted list. Under the covers it uses `list.sort()` to leverage on Python’s “supernatural” sorting speed in cases of pre-existing order. Then it just chops the result up into contiguous sublists, a very fast linear-time operation, ---
**Author:** ![dg-pb](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/dg-pb/32/16248_2.png) [@dg-pb](https://discuss.python.org/u/dg-pb)\ **Post date:** [July 3, 2026, 6:05pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/19 "2026-07-03T18:05:43Z")
> [@tim.one](#): > > Grant did _major_ testing against all available alternatives (including C extensions for B trees, AVL tress, red-black trees, …) I have no doubt that at a time it was A class work. And indeed - there is nothing faster out there - I was surprised how it surpassed things implemented in `C`. What I am saying is that my new digs suggest that there might be better alternatives. For example. Tiered-vector (2nd order) based sort (fully in-place) has resulted in only 2x slower performance than TimSort with the same level of optimization. And my benchmarks of `sortedcontainers` don’t give an indication that it can do better without at least coding it up in `C` - especially for sizes up to 100K, where pure Python constants are quite high. Even if `sortedcontainers` turn out to be the best approach, there are opportunities to optimize - both macro and micro. e.g. my alternative implementation has 10x faster ` __getitem__ `. * * * I don’t mind elaborating more on my findings / share code if there was a technical thread to push this. And if someone is going to push it - please make such thread first - at worst (or best - depending on POV) you will prove me wrong. ---
**Author:** ![jsbueno](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/jsbueno/32/1210_2.png) [@jsbueno](https://discuss.python.org/u/jsbueno)\ **Post date:** [July 4, 2026, 2:45am UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/20 "2026-07-04T02:45:30Z")
My point is that both ‘bisect’ and heapq could use a nice class wrapper - so one doesn’t need the external “l” and have to worry about nobody shuffling it around. That is even doubly truth in these days of static type checking - and maybe it can be the most compelling argument here: static type checkers have no way to know a list being kept to be used with bisect or heapq should not be modified by methods other than those. Having a wrapper class with “push” “pop” (and maybe some other amenities) instantly solves that. ---
**Author:** ![facundo](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/facundo/32/53_2.png) [@facundo](https://discuss.python.org/u/facundo)\ **Post date:** [July 4, 2026, 12:38pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/21 "2026-07-04T12:38:32Z")
@jsbueno I agree with you. I had [this idea](https://mail.python.org/pipermail/python-ideas/2009-April/004173.html) 17 years ago (wow!), maybe it’s time to push for it 🙂 ---
**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\ **Post date:** [July 4, 2026, 7:50pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/22 "2026-07-04T19:50:02Z")
> [@facundo](#): > > had [this idea](https://mail.python.org/pipermail/python-ideas/2009-April/004173.html) 17 years ago (wow!), maybe it’s time to push for it 🙂 +1! @rhettinger was agreeable at the time, so if’s surprisig nothing came of it then., @guido never subscribed to “OO religion”, so “it could be more OO” never carried much weight. There was a long tradition of coding heaps in C as plain old vectors, and that’s adequate for most real uses. But Python only supported min heaps, and the “plain old list” API became error-prone when it went on to support max heaps too. Now that’s dealt with via tedious name near-duplication, like `heappush()` for (the original) min heaps, and `heappusg_max()` for (the newer) max heaps, Life would be better all around if the type of heap wanted were established at initialization time, with the same method names used for all. But there’s also that heaps are rarely the best choice.. For example, priority queues are generally better handled by `SortedList` (which requires fewer comparisons, and is equally good at handling min- and max-queues), and n-way merging by some form of tournament tree (which some versions oif PyPy use to implement `heaoq.merge()`, not using heaps at all). Heaps remain the best choice in one application aree: sorting when - It must be done in-place (essentially no extra memory, not even for O(\log{n}) temp stack space). - Guaranteed worst-case O(n \log{n}) runtine, - You don’t care about stability, - You don’t care about possibilities for exploiting pre-existing order (the best case for plain heapsort is also O(n \log{n}) runtime) But that’s become quite a niche use case too. [Next page](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994.md?page=2)