[Python-ideas] Multiple level sorting in python where the order of some levels may or may not be reversed

[Tim Peters]

[Sven R. Kunze <srkunze at mail.de>]
> Indeed. I also didn't know about that detail of reversing. :) Amazing. (Also
> welcome to the list, Alireza.)

It follows from what the docs say, although I'd agree it may be
helpful if the docs explicitly spelled out this consequence (that
reverse=True also preserves the original order of equal elements - as
the docs say, it's not that the _list_ "is reversed", is that "list
elements are sorted as if each comparison were reversed").


> Do you think that simple solution could have a chance to be added to stdlib
> somehow (with the possibility of speeding it up in the future)?

Well, the sorting "how to" already explains the basic idea.  The
`.sort()` docs also explain that stability "is helpful for sorting in
multiple passes (for example, sort by department, then by salary
grade)".

I suspect I know too much about this to be of any use in judging
what's missing ;-)

Speeding it wouldn't be easy - or usually necessary.  The obvious
"improvement" would do it all in a single `.sort()` invocation.  But
calling back into Python code to do fancy, multi-step comparisons is
so expensive that I expect it would take a large N for saving some
additional worst-case O(N*log(N)) sorting steps to repay the cost.

If you'd like to play with that, here's a different `multisort()`
implementation.  Again `specs` is a list of (key_function,
True-for-reverse) tuples, most-significant key first.  And, again, no
assumptions are made about what key functions return, and the sort
continues to guarantee that only "<" comparisons are made:

    def _sorter(specs):
        keyfuncs, reversers = zip(*specs)

        class Wrapper(object):
            def __init__(self, obj):
                self.keys = tuple(f(obj) for f in keyfuncs)

            def __lt__(x, y):
                for a, b, r in zip(x.keys, y.keys, reversers):
                    if a < b:
                        return not r
                    if b < a:
                        return r
                return False    # all the keys are equal

        return Wrapper

    def multisort(xs, specs):
        xs.sort(key=_sorter(specs))