bearophileh...@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 -- http://mail.python.org/mailman/listinfo/python-list
