[Python-Dev] decorate-sort-undecorate

[John Williams]

Guido van Rossum wrote:
> Given that internally we still do a DSU, sorting tuples of (key,
> something), using the id of the record for 'something' is just as
> inefficient as using the original index -- in both cases we'd have to
> allocate len(lst) ints.
> 
> Greg Ewing suggested that the ints shouldn't have to be Python ints.
> While this is true, it would require a much larger overhaul of the
> existing sort code, which assumes the "records" to be sorted are
> pointers to objects.

Why not use a special tuple type for the DSU algorithm that ignores its 
last element when doing a comparison? It eliminates the problem of 
creating a zillion int objects, and <speculation>it would be easy to 
implement.</speculation>

jw