[Python-Dev] decorate-sort-undecorate

[Tim Peters]

[Fred]
>> 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.

[Guido]
> I can't tell if that'll work, but if it does, it would be a great
> solution.

I mentioned that before -- doubling the amount of data movement would hurt,
at best by blowing cache all to hell.

There's a related approach, though:  build a distinct vector of custom
objects, each containing:

1. A pointer to the key.
2. The original index, as a C integer.

This is similar to, but smaller than, something mentioned before.

The comparison function for this kind of object redirects to comparing only
the keys -- the integers are ignored during the sort.  Sort this list with
the sorting code exactly as it exists now.

At the end of sorting, the integer members can be used to permute the
original list into order.  This can be done in-place efficiently (not
entirely obvious; Knuth gives at least one algorithm for it).