Ordered dict by default

Delaney, Timothy (Tim) tdelaney at avaya.com
Mon Feb 9 00:31:36 CET 2009


bearophileHUGS at lycos.com wrote:

> I have missed another example: It may be possible to create a sorting
> routine that's not stable but is faster than the current stable
> timsort (for example in C++ STL you have both sorting routines, and
> the unstable one is a variant of introsort that is faster than the
> stable version). I think Python will keep the stable one, because even
> if (in theory. In practice it may be quite difficult to write such
> unstable sorter faster than timsort) it can be slower, it's safer and
> more useful than an unstable sort.

Python mandates a stable sort, so this will not change. Note that this
used to not be the case - timsort was introduced in Python 2.3, and
*because* it was *both* stable and blazingly fast, the requirement for a
stable sort was back-dated to Python 2.3.

If timsort had not been so overwhelmingly superior to every other option
at the time (and in particular, without any known worst-case scenarios)
then Python would likely still not be requiring a stable sort. But
because it is so good, the extra performance gain from any future
non-stable sort was considered unlikely to offset the benefits of a
stable sort.

Tim Delaney



More information about the Python-list mailing list