outline-style sorting algorithm

[Delaney, Timothy C (Timothy)]

Thorsten Kampe wrote:

>>     def sorted (seq, cmp=None, key=None):
> 
> What is 'cmp=None' for?

To have the same semantics as 2.4 `sorted`. In 2.4 `list.sort` and
`sorted` can take either or both of `cmp` and `key`. If `key` is passed,
the keys are generated. If `cmp` is passed then that comparison function
is used to sort the *keys* (and only the keys). Of course, if `key` is
not passed then the keys used are the objects themselves.

>>         if key is None:
>>             return seq
>>         else:
>>             return [i[-1] for i in seq]
> 
> What is 'key=None' for? Is that for speeding up if someone wants to
> pass the indentity function (f(x)=x; lambda x: x)?

Nope - if no `key` function is passed, the objects themselves are used
in the sort.

>> Note that Python 2.4 will have DSU as a built-in idiom to `list.sort`
>> i.e. `list.sort(key=func)` but will be somewhat more efficient than
>> the above. Likewise there will be a new builtin `sorted` which has
>> exactly the same semantics as the above - it is stable, and it does
>> not ever compare the actual value if a key function is supplied -
>> only the key value (the above also compares the position, but that's
>> an implementation detail and has no visible effect).
> 
> If it has no visible effects than it would be useless. In my opinion
> it has the effect that two items that have the same func(x) stay in
> the same position as before. Is that desirable? Was that your goal?

Sorry - I didn't explain this well enough. In my implementation, I'm
using the indices as a termination condition. Since all the indices are
different integers, I'm guaranteed that the objects themselves will
never be compared. I don't actually need them there to ensure that the
sort is stable since the 2.3 sort method is itself stable.

In the 2.4 sort, the indices themselves are never used or needed - since
the sort is in C it's much easier to ensure that just the keys are
sorted without falling back to the object, but still easily maintain
where the object will end up. In Python code it's much simpler to just
stick them into the same tuple, but then you do need to ensure that the
object won't be used in the comparison.

Tim Delaney