[Python-Dev] decorate-sort-undecorate

[Fred L. Drake, Jr.]

Guido van Rossum writes:
 > If we're going to do a custom object, it should be a fixed-length
 > struct containing (1) the key, (2) a C int of sufficient size to hold
 > the record index; (3) a pointer to the record, and its comparison
 > should only use (1) and (2).

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

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.


  -Fred

-- 
Fred L. Drake, Jr.  <fdrake at acm.org>
PythonLabs at Zope Corporation