[Python-Dev] decorate-sort-undecorate

[Delaney, Timothy C (Timothy)]

> From: Greg Ewing [mailto:greg at cosc.canterbury.ac.nz]
> 
> Guido:
> 
> > > 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.

How would we document this? To date sort() gives no guarantees about stability. We could continue to give this lack of guarantee by stating that only the key as returned from the key function is used in the comparison. Alternatively, we could guarantee that the resulting sort will be stable (which would make it incumbent to use the index if an unstable sort is introduced in a future version).

Personally, I think it would be a good idea to make the guarantee that from 2.3 sort() will be stable when the comparison function returns equal, or the keys compare equal, or the objects compare equal (in the case of no comparison func or key func). But that could just be me.

Tim Delaney