How can I get 2.x-like sorting behaviour in Python 3.x?

I'm trying to replicate (and if possible improve on) Python 2.x's sorting behaviour in 3.x, so that mutually orderable types like int, float etc. are sorted as expected, and mutually unorderable types are grouped within the output.

Here's an example of what I'm talking about:

    >>> sorted([0, 'one', 2.3, 'four', -5])  # Python 2.x
    [-5, 0, 2.3, 'four', 'one']
    >>> sorted([0, 'one', 2.3, 'four', -5])  # Python 3.x
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unorderable types: str() < int()

My previous attempt at this, using a class for the key parameter to sorted() (see Why does this key class for sorting heterogeneous sequences behave oddly?) is fundamentally broken, because its approach of

  1. Trying to compare values, and
  2. If that fails, falling back to comparing the string representation of their types

can lead to intransitive ordering, as explained by BrenBarn's excellent answer.

A naïve approach, which I initially rejected without even trying to code it, would be to use a key function that returns a (type, value) tuple:

    def motley(value):
        return repr(type(value)), value

However, this doesn't do what I want. In the first place, it breaks the natural ordering of mutually orderable types:

    >>> sorted([0, 123.4, 5, -6, 7.89])
    [-6, 0, 5, 7.89, 123.4]
    >>> sorted([0, 123.4, 5, -6, 7.89], key=motley)
    [7.89, 123.4, -6, 0, 5]

Secondly, it raises an exception when the input contains two objects of the same intrinsically unorderable type:

    >>> sorted([{1:2}, {3:4}], key=motley)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unorderable types: dict() < dict()

... which admittedly is the standard behaviour in both Python 2.x and 3.x – but ideally I'd like such types to be grouped together (I don't especially care about their ordering, but it would seem in keeping with Python's guarantee of stable sorting that they retain their original order).

I can work around the first of these problems for numeric types by special-casing them:

    from numbers import Real
    from decimal import Decimal

    def motley(value):
        numeric = Real, Decimal
        if isinstance(value, numeric):
            typeinfo = numeric
            typeinfo = type(value)
        return repr(typeinfo), value

... which works as far as it goes:

    >>> sorted([0, 'one', 2.3, 'four', -5], key=motley)
    [-5, 0, 2.3, 'four', 'one']

... but doesn't account for the fact that there may be other distinct (possibly user-defined) types which are mutually orderable, and of course still fails with intrinsically unorderable types:

    >>> sorted([{1:2}, {3:4}], key=motley)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unorderable types: dict() < dict()

Is there another approach which solves both the problem of arbitrary, distinct-but-mutually-orderable types and that of intrinsically unorderable types?

Stupid idea: make a first pass to divide all the different items in groups that can be compared between each other, sort the individual groups and finally concatenate them. I assume that an item is comparable to all members of a group, if it is comparable with the first member of a group. Something like this (Python3):

    import itertools

    def python2sort(x):
        it = iter(x)
        groups = [[next(it)]]
        for item in it:
            for group in groups:
                    item < group[0]  # exception if not comparable
                except TypeError:
            else:  # did not break, make new group
        print(groups)  # for debugging
        return itertools.chain.from_iterable(sorted(group) for group in groups)

This will have quadratic running time in the pathetic case that none of the items are comparable, but I guess the only way to know that for sure is to check all possible combinations. See the quadratic behavior as a deserved punishment for anyone trying to sort a long list of unsortable items, like complex numbers. In a more common case of a mix of some strings and some integers, the speed should be similar to the speed of a normal sort. Quick test:

    In [19]: x = [0, 'one', 2.3, 'four', -5, 1j, 2j,  -5.5, 13 , 15.3, 'aa', 'zz']

    In [20]: list(python2sort(x))
    [[0, 2.3, -5, -5.5, 13, 15.3], ['one', 'four', 'aa', 'zz'], [1j], [2j]]
    Out[20]: [-5.5, -5, 0, 2.3, 13, 15.3, 'aa', 'four', 'one', 'zz', 1j, 2j]

It seems to be a 'stable sort' as well, since the groups are formed in the order the incomparable items are encountered.