[Python-ideas] Optimizing list.sort() by checking type in advance

[Chris Angelico]

On Tue, Oct 11, 2016 at 2:41 PM, Elliot Gorokhovsky
<elliot.gorokhovsky at gmail.com> wrote:
> Oh no, the idea here is just you would copy over the floats associated with
> the PyObject* and keep them in an array of such structs, so that we know
> which PyObject* are associated with which floats. Then after the standard
> library quicksort sorts them you would copy the PyObject* into the list. So
> you sort the PyObject* keyed by the floats. Anyway, I think the copying back
> and forth would probably be too expensive, it's just an idea.

It also wouldn't work if you have more than one object with the same value.

>>> x = 1.0
>>> y = 2.0/2
>>> x is y
False
>>> l = [x, y, x]
>>> l.sort()
>>> assert l[0] is x
>>> assert l[1] is y
>>> assert l[2] is x

Python's sort is stable, so the three elements of the list (being all
equal) must remain in the same order.

ChrisA