Q: sort's key and cmp parameters

[Raymond Hettinger]

On Oct 1, 10:08 am, kj <no.em... at please.post> 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.

If you're assuming a consistent sort-order (transitivity, not
evolving over time, etc), then the cmp method and key method
are mathematically equivalent (you could always do a compare
sort first, record the order produced, and assign the position
number as a key function):

    # constructive proof of the existence of a key function
    # corresponding to a given cmp function
    tmplist = sorted(s, cmp=mycmp)
    pos = dict(zip(map(id, tmplist), range(len(tmplist))))
    result = sorted(s, key=lambda x: pos[id(x)])
    assert tmplist == result

Given equivalence, what is really at stake is convenience.

If you're starting point is a cmp function (for instance,
asking a dating service member whether they prefer
mate x to mate y), then having to convert to a key function
can be inconvenient.

If you need to sort by an ascending primary key and a descending
secondary key, you may find it easiest to sort in two passes
(taking advantage of guaranteed sort stability):

    sorted(s, key=secondary, reversed=True)
    sorted(s, key=primary)

With a cmp function, the above could be achieved in a single pass:

    def mycmp(x, y):
         p = cmp(primary(a), primary(b))
         return p if p else cmp(secondary(b), secondary(a))

    sorted(s, cmp=mycmp)

Also, as Paul pointed-out, there are some structures such as tree
comparisons that may be challenging to express directly as a key
function.  As Carsten pointed-out, the cmp2key function allows
cmp functions to trivially (though indirectly) be recast as key
functions.

All that being said, for many everyday uses, a key function is
simpler to write and faster to run than a cmp function approach.


Raymond