[Python-Dev] decorate-sort-undecorate

Guido van Rossum guido at python.org
Tue Oct 14 10:50:36 EDT 2003

> I have and have seen many use cases where the things being sorted
> are dictionaries (comparisons can be costlier) or instances (they can
> be non-comparable).
> I agree that the "stable" nature of sorting is not all that important in
> our context.  But avoiding whole-record comparison in the general
> case seems important enough to me that I'd accept any arbitrary
> non-comparing behavior (e.g. making the id of the thing being sorted
> the secondary key!-) rather than default to whole-record compares.

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.

--Guido van Rossum (home page: http://www.python.org/~guido/)

More information about the Python-Dev mailing list