[Python-Dev] decorate-sort-undecorate

[Raymond Hettinger]

[Fred L. Drake]
> As has been pointed out, we already have a stable sort.  Instead of
> making stability an option, let's just keep it.

Right.  If a fast tie-breaker is provided, why would anyone ever choose
stable=False?

 
> We could allocate a second array of PyObject* to mirror the list
> contents; that would have only the keys.  When two values are switched
> in the sort, the values in both the key list and the value list can be
> switched.  When done, we only need to decref the computed keys and
> free the array of keys.
> 
> No additional structures would be needed.

I would rather wrap Tim's existing code than muck with assignment logic.
Ideally, the performance of list.sort() should stay unchanged when the
key function is not specified.

Tim's original (key, index, value) idea seems to be simplest.  The only
sticking point is the immortality of PyInts.  One easy, but not so
elegant way around this is to use another mortal object for a tiebreaker
(for example, "00000", "00001", ...).  Alternatively, is there a way of
telling a PyInt to be mortal?

Besides immortality and speed, another consideration is the interaction
between the cmp function and the key function.  If both are specified,
then the underlying decoration becomes visible to the user:

    def viewcmp(a, b):
        print a, b  # the decoration just became visible
        return cmp(a,b)
    mylist.sort(cmp=viewcmp, key=str.lower)

Since the decoration can be visible, it should be as understandable as
possible.  Viewed this way, PyInts are preferable to a custom object.


Raymond Hettinger