[Python-Dev] decorate-sort-undecorate

Guido van Rossum guido at python.org
Tue Oct 14 21:52:04 EDT 2003

> > > Don't you still need a tie-breaker index to preserve stability?
> > 
> > No, because the sort algorithm is already stable.
> In which case it makes no sense at all for stability
> to be an option, since you'd have to go out of your
> way to make it *un*stable!
> The only issue then is to avoid comparing the whole
> record, and this presumably should be non-optional
> as well.

Right.  I think we've settled on using small wrapper objects instead
of tuples, whose comparison *only* compares the key value, and whose
other field contains a reference to the full record.  When passing
both cmp and key, cmp is passed the key field from the wrapper.

The wrapper objects don't need to have any general purpose
functionality so their implementation should be very simple.  (We
*could* go further and have a custom allocator for these objects, but
I'm not sure that that's necessary -- pymalloc should be fast enough,
and the bulk cost is going to be the O(N log N) behavior of the sort

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

More information about the Python-Dev mailing list