Q: sort's key and cmp parameters

[Paul Rubin]

Raymond Hettinger <python at rcn.com> writes:
> So, it looks like the relevant comparison values can be stored in
> nested lists:
> 
>    list_of_lists = \
>      [[1, [3, [], []],
>           [7, [5, [], []], []]],
>       [19, [23, [], []],
>           []],
>      ]

Now you've copied all the data out of the original tree, which is even
worse than putting a class wrapper around it.  The comparison remains
(asymptotically) as expensive as before, too.

> Are there any of these trees that cannot be transformed
> (by a key function) into an equivalent nested list of lists
> and values so that the trees can be directly compared to one another
> using Python's normal built-in recursive comparison order for lists?

I think so.  Say you want to change the numeric comparisons so that
even numbers always sort before odd numbers, ie.
    -4 < -2 < 0 < 2 < 4 < ... < -999 < ... -1 < 1 < 3 ...
I don't think there is a way to re-encode the numbers so they
can be compared with direct integer comparison.  Even if there is,
I think there are reasonable orderings on the trees themselves that
can't possibly be embedded in the standard python comparison order.
I might be able to construct an example using ordinal diagrams from
proof theory.