Q: sort's key and cmp parameters

[Peter Otten]

kj wrote:

> Challenge: to come up with a sorting task that cannot be achieved
> by passing to the sort method (or sorted function) suitable values
> for its key and reverse parameters, but instead *require* giving
> a value to its cmp parameter.
> 
> For example,
> 
> from random import random
> scrambled = some_list.sort(cmp=lambda x, y: cmp(random(), 0.5))

The above violates the transitivity requirement as stated below. The result 
will have a bias.

> can be achieved (to a very good approximation at least) with
> 
> scrambled = some_list.sort(key=lambda x: random())
> 
> Is there a real-life sorting task that requires (or is far more
> efficient with) cmp and can't be easily achieved with key and
> reverse?

The core developers don't think there is one. list.sort() no longer supports 
the cmp parameter in 3.x.
 
> Many thanks in advance,
> 
> G.
> 
> P.S. I guess that, if sort is going to produce a non-trivial,
> *consistent* order, a function CMP passed as the value of its cmp
> parameter must satisfy the following properties:
> 
> 0. CMP(x, y) must be non-zero for some elements x, y of the list;
> 1. anti-symmetry: sign(CMP(x, y)) must be equal to -sign(CMP(y, x));
> 2. transitivity: if sign(CMP(x, y)) equals sign(CMP(y, z)), then
>    sign(CMP(x, z)) must be equal to sign(CMP(x, y)).
> 
> In (1) and (2), sign() stands for the function
> 
>             -1 if x  < 0
>   sign(x) =  0 if x == 0
>              1 if x  > 0
> 
> I suppose that all bets are off if these properties are not satisfied,
> though the documentation does not make this entirely clear, as far
> as I can tell.  (If I'm wrong about this alleged omission, please
> point me to the part of the docs that I missed.)