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

Question

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
    else:
        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?

Watereddown

Just a little note: Python 2's default behavior is itself potentially intransitive, so there's no ultimate solution. Modifying my example from the other question, with Python 2, b'z' < (1, 2) < u'a' < b'z' (because 'str' < 'tuple' < 'unicode', but str and unicode are value-comparable in Python 2. I'm curious, though, what your actual use case is for wanting to do this for arbitrary types (instead of just "manually" grouping, say, numeric types). – Compound

@Compound mostly idle curiosity - the starting point was wondering how pprint goes about displaying dictionaries with the keys in order, and being more in a mood to think it through than go look at the source. Actually, I should probably go do that now :-) – Watereddown

... and, it turns out to use a variation on the motley class from my previous question! The use of a (str(type(obj)), id(obj)) return value is presumably to mitigate the problems you raised with that approach, although I don't think it can do so completely. – Watereddown

Yeah. I mean, all it's trying to do is get something that will look reasonable when it's printed. I don't think they were concerned with trying cover every possible corner case. In fact, just playing around with it now, I was able to get it to print values out of order by creating dicts with funky keys. – Compound

Answer 1

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:
            try:
                item < group[0]  # exception if not comparable
                group.append(item)
                break
            except TypeError:
                continue
        else:  # did not break, make new group
            groups.append([item])
    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.

Tuberculin

Answer 2

This answer aims to faithfully re-create the Python 2 sort order, in Python 3, in every detail.

The actual Python 2 implementation is quite involved, but object.c's default_3way_compare does the final fallback after instances have been given a chance to implement normal comparison rules. This is after individual types have been given a chance to compare (via the __cmp__ or __lt__ hooks).

Implementing that function as pure Python in a wrapper, plus emulating the exceptions to the rules (dict and complex numbers specifically) gives us the same Python 2 sorting semantics in Python 3:

from numbers import Number


# decorator for type to function mapping special cases
def per_type_cmp(type_):
    try:
        mapping = per_type_cmp.mapping
    except AttributeError:
        mapping = per_type_cmp.mapping = {}
    def decorator(cmpfunc):
        mapping[type_] = cmpfunc
        return cmpfunc
    return decorator


class python2_sort_key(object):
    _unhandled_types = {complex}

    def __init__(self, ob):
       self._ob = ob

    def __lt__(self, other):
        _unhandled_types = self._unhandled_types
        self, other = self._ob, other._ob  # we don't care about the wrapper

        # default_3way_compare is used only if direct comparison failed
        try:
            return self < other
        except TypeError:
            pass

        # hooks to implement special casing for types, dict in Py2 has
        # a dedicated __cmp__ method that is gone in Py3 for example.
        for type_, special_cmp in per_type_cmp.mapping.items():
            if isinstance(self, type_) and isinstance(other, type_):
                return special_cmp(self, other)

        # explicitly raise again for types that won't sort in Python 2 either
        if type(self) in _unhandled_types:
            raise TypeError('no ordering relation is defined for {}'.format(
                type(self).__name__))
        if type(other) in _unhandled_types:
            raise TypeError('no ordering relation is defined for {}'.format(
                type(other).__name__))

        # default_3way_compare from Python 2 as Python code
        # same type but no ordering defined, go by id
        if type(self) is type(other):
            return id(self) < id(other)

        # None always comes first
        if self is None:
            return True
        if other is None:
            return False

        # Sort by typename, but numbers are sorted before other types
        self_tname = '' if isinstance(self, Number) else type(self).__name__
        other_tname = '' if isinstance(other, Number) else type(other).__name__

        if self_tname != other_tname:
            return self_tname < other_tname

        # same typename, or both numbers, but different type objects, order
        # by the id of the type object
        return id(type(self)) < id(type(other))


@per_type_cmp(dict)
def dict_cmp(a, b, _s=object()):
    if len(a) != len(b):
        return len(a) < len(b)
    adiff = min((k for k in a if a[k] != b.get(k, _s)), key=python2_sort_key, default=_s)
    if adiff is _s:
        # All keys in a have a matching value in b, so the dicts are equal
        return False
    bdiff = min((k for k in b if b[k] != a.get(k, _s)), key=python2_sort_key)
    if adiff != bdiff:
        return python2_sort_key(adiff) < python2_sort_key(bdiff)
    return python2_sort_key(a[adiff]) < python2_sort_key(b[bdiff])

I incorporated handling dictionary sorting as implemented in Python 2, since that'd be supported by the type itself via a __cmp__ hook. I've stuck to the Python 2 ordering for the keys and values as well, naturally.

I've also added special casing for complex numbers, as Python 2 raises an exception when you try sort to these:

>>> sorted([0.0, 1, (1+0j), False, (2+3j)])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers

You may have to add more special cases if you want to emulate Python 2 behaviour exactly.

If you wanted to sort complex numbers anyway you'll need to consistently put them with the non-numbers group; e.g.:

# Sort by typename, but numbers are sorted before other types
if isinstance(self, Number) and not isinstance(self, complex):
    self_tname = ''
else:
    self_tname = type(self).__name__
if isinstance(other, Number) and not isinstance(other, complex):
    other_tname = ''
else:
    other_tname = type(other).__name__

Some test cases:

>>> sorted([0, 'one', 2.3, 'four', -5], key=python2_sort_key)
[-5, 0, 2.3, 'four', 'one']
>>> sorted([0, 123.4, 5, -6, 7.89], key=python2_sort_key)
[-6, 0, 5, 7.89, 123.4]
>>> sorted([{1:2}, {3:4}], key=python2_sort_key)
[{1: 2}, {3: 4}]
>>> sorted([{1:2}, None, {3:4}], key=python2_sort_key)
[None, {1: 2}, {3: 4}]

Fulgent

Impressive effort to capture all the idiosyncrasies of Python 2 sort, but can't you make use of functools.cmp_to_key() like I suggest here: https://mcmap.net/q/322784/-how-can-i-get-2-x-like-sorting-behaviour-in-python-3-x Or I'm overlooking something? – Gathard

@Chris_Rands: cmp_to_key produces an object that provides a __lt__ method, just like my solution. (It offers the full range of rich comparison methods, but only __lt__ really matters). – Fulgent

worked so far for us! great work :) some of our infra was really reliant on this behaviour, and not having this would really block the migration to py3. Perhaps something like this should be provided in the six compat library – Hokkaido

This doesn't preserve Py2 behaviour with custom types that implement equality/comparator functions, if those are nested in e.g. tuples or lists, and raise a TypeError when compared with other types. e.g. >>> sorted([(MyObj("foo"), 1),(2, MyObj("bar"))]) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 12, in eq TypeError: Need to compare MyObj >>> sorted([(MyObj("foo"), 1),(2, MyObj("bar"))], key=python2_sort_key) [(MyObj('foo'), 1), (2, MyObj('bar'))] This is because it falls back to an id comparison if the types are the same. – Valetudinary

To handle this case we can declare a custom handler for tuples and lists in the same way we did for dicts, that then compare each element with the comparator: @per_type_cmp(tuple) def tuple_cmp(a, b): for index in range(min(len(a), len(b))): comp = (python2_sort_key(b[index], a[index])) - (python2_sort_key(a[index], b[index])) if comp != 0: return comp < 0 # All checked values in tuple are equal, shorter one is ordered first return len(a) <= len(b) – Valetudinary

Answer 3

Not running Python 3 here, but maybe something like this would work. Test to see if doing a "less than" compare on "value" creates an exception and then do "something" to handle that case, like convert it to a string.

Of course you'd still need more special handling if there are other types in your list that are not the same type but are mutually orderable.

from numbers import Real
from decimal import Decimal

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

    try:
        x = value < value
    except TypeError:
        value = repr(value)

    return repr(typeinfo), value

>>> print sorted([0, 'one', 2.3, 'four', -5, (2+3j), (1-3j)], key=motley)
[-5, 0, 2.3, (1-3j), (2+3j), 'four', 'one']

Erythro

Oops, you got really lucky in that Zero awarded the bounty to you by mistake! Since this cannot be undone, congrats on your lucky break! :-) – Fulgent

It won't reproduce the Python 2 sort order, however. – Fulgent

Well, if you look at his question details, he wasn't caring too much that it EXACTLY duplicate python 2. He seems most concerned with just handling different types gracefully and not crashing. "I'm trying to replicate (and if possible improve on) Python 2.x's sorting behaviour". I'm not even sure if the different python 2 versions would guarantee the same sort order between them. – Erythro

There is no guarantee about the sort order, but it hasn't changed either across all the 2.x versions at the very least. – Fulgent

True, but despite the title of the question, the main concern is not exact python 2 replication. What he wants is: "Is there another approach which solves both the problem of arbitrary, distinct-but-mutually-orderable types and that of intrinsically unorderable types?" My answer does, and it only requires one minor mod to his original code. – Erythro

There was a history here, where Zero asked another question before this one, and where we discussed the issue in the chatroom. I wrote my answer to show how the Python 2 implementation works, which is a lot more complex than meets the eye at first. – Fulgent

But given that the question he asked doesn't want 2.x sorting, only "2.x like" sorting, why would you go to all that trouble? The question as it appears now goes into explicit detail about what he needs, and exact duplication of 2.x sorting isn't it. – Erythro

Because Zero lowered his expectations. The first sentence of the question still reads I'm trying to replicate [...] Python 2.x's sorting behaviour in 3.x. – Fulgent

Actually it reads "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." I say the simplest solution that does the job is best. – Erythro

If it read "I'm trying to replicate Python 2.x's sorting behaviour in 3.x, so that I can easily port old code that is relying on the 2.x sort order", then I would agree your answer is much better. – Erythro

Answer 4

One way for Python 3.2+ is to use functools.cmp_to_key(). With this you can quickly implement a solution that tries to compare the values and then falls back on comparing the string representation of the types. You can also avoid an error being raised when comparing unordered types and leave the order as in the original case:

from functools import cmp_to_key

def cmp(a,b):
    try:
        return (a > b) - (a < b)
    except TypeError:
        s1, s2 = type(a).__name__, type(b).__name__
        return (s1 > s2) - (s1 < s2)

Examples (input lists taken from Martijn Pieters's answer):

sorted([0, 'one', 2.3, 'four', -5], key=cmp_to_key(cmp))
# [-5, 0, 2.3, 'four', 'one']
sorted([0, 123.4, 5, -6, 7.89], key=cmp_to_key(cmp))
# [-6, 0, 5, 7.89, 123.4]
sorted([{1:2}, {3:4}], key=cmp_to_key(cmp))
# [{1: 2}, {3: 4}]
sorted([{1:2}, None, {3:4}], key=cmp_to_key(cmp))
# [None, {1: 2}, {3: 4}]

This has the disadvantage that the three-way compare is always conducted, increasing the time complexity. However, the solution is low overhead, short, clean and I think cmp_to_key() was developed for this kind of Python 2 emulation use case.

Gathard

cmp_to_key was developed to make it possible to re-use existing cmp() functions. Under the hood it does exactly what my solution does: delegate to a __lt__ method on a key object, see How does Python's cmp_to_key function work? So your solution is basically a simplified version of my python2_sort_key.__lt__() method, and for a, b read self, other, but adding the complication of having to return an integer value relative to 0. – Fulgent

Your solution doesn't handle dictionaries (try sorting [{3:4}, {1: 2}]) or None or numeric values correctly. All that can be added in, but you are then still just implementing the same logic that my solution a already offers, but with the disadvantage that you have to produce that 3-way integer number again rather than a boolean. – Fulgent

@MartijnPieters Thanks for the feedback. I certainly don't think my solution is as comprehensive as yours but it seems like a reasonable lightweight option for those seeking this kind of functionality. Sorting [{3:4}, {1: 2}] returns the same order as the input, which is as I describe (I'm not sure what is desired for this case) – Gathard

See Is there a description of how __cmp__ works for dict objects in Python 2? for the Python 2 behaviour for dictionaries. – Fulgent

@MartijnPieters Indeed, well I did already say in my answer that is has this disadvantage of always doing the 3-way-compare and I agree more could be added depending on the exact desired specification of sort, but I'll leave my answer like this. I'm not expecting the bounty you know, even via a misclick ;) – Gathard

I wasn't worried about the bounty ;-) Just providing feedback on your cmp_to_key approach and how it performs vis-a-vis the Python 2 sort. – Fulgent

Answer 5

I tried to implement the Python 2 sorting c code in python 3 as faithfully as possible.

Use it like so: mydata.sort(key=py2key()) or mydata.sort(key=py2key(lambda x: mykeyfunc))

def default_3way_compare(v, w):  # Yes, this is how Python 2 sorted things :)
    tv, tw = type(v), type(w)
    if tv is tw:
        return -1 if id(v) < id(w) else (1 if id(v) > id(w) else 0)
    if v is None:
        return -1
    if w is None:
        return 1
    if isinstance(v, (int, float)):
        vname = ''
    else:
        vname = type(v).__name__
    if isinstance(w, (int, float)):
        wname = ''
    else:
        wname = type(w).__name__
    if vname < wname:
        return -1
    if vname > wname:
        return 1
    return -1 if id(type(v)) < id(type(w)) else 1

def py2key(func=None):  # based on cmp_to_key
    class K(object):
        __slots__ = ['obj']
        __hash__ = None

        def __init__(self, obj):
            self.obj = func(obj) if func else obj

        def __lt__(self, other):
            try:
                return self.obj < other.obj
            except TypeError:
                return default_3way_compare(self.obj, other.obj) < 0

        def __gt__(self, other):
            try:
                return self.obj > other.obj
            except TypeError:
                return default_3way_compare(self.obj, other.obj) > 0

        def __eq__(self, other):
            try:
                return self.obj == other.obj
            except TypeError:
                return default_3way_compare(self.obj, other.obj) == 0

        def __le__(self, other):
            try:
                return self.obj <= other.obj
            except TypeError:
                return default_3way_compare(self.obj, other.obj) <= 0

        def __ge__(self, other):
            try:
                return self.obj >= other.obj
            except TypeError:
                return default_3way_compare(self.obj, other.obj) >= 0
    return K

Bibliogony

Thank you, this is an excellent answer and does the best job at replicating the old behaviour. I will cross link to this from other related questions. – Donn

Thanks. Could I use this in an open source project? – Tello

Answer 6

We can solve this problem in the following way.

1. Group by type.
2. Find which types are comparable by attempting to compare a single representative of each type.
3. Merge groups of comparable types.
4. Sort merged groups, if possible.
5. yield from (sorted) merged groups

We can get a deterministic and orderable key function from types by using repr(type(x)). Note that the 'type hierarchy' here is determined by the repr of the types themselves. A flaw in this method is that if two types have identical __repr__ (the types themselves, not the instances), you will 'confuse' types. This can be solved by using a key function that returns a tuple (repr(type), id(type)), but I have not implemented that in this solution.

The advantage of my method over Bas Swinkel's is a cleaner handling of a group of un-orderable elements. We do not have quadratic behavior; instead, the function gives up after the first attempted ordering during sorted()).

My method functions worst in the scenario where there are an extremely large number of different types in the iterable. This is a rare scenario, but I suppose it could come up.

def py2sort(iterable):
        by_type_repr = lambda x: repr(type(x))
        iterable = sorted(iterable, key = by_type_repr)
        types = {type_: list(group) for type_, group in groupby(iterable, by_type_repr)}

        def merge_compatible_types(types):
            representatives = [(type_, items[0]) for (type_, items) in types.items()]

            def mergable_types():
                for i, (type_0, elem_0) in enumerate(representatives, 1):
                    for type_1, elem_1 in representatives[i:]:
                         if _comparable(elem_0, elem_1):
                             yield type_0, type_1

            def merge_types(a, b):
                try:
                    types[a].extend(types[b])
                    del types[b]
                except KeyError:
                    pass # already merged

            for a, b in mergable_types():
                merge_types(a, b)
            return types

        def gen_from_sorted_comparable_groups(types):
            for _, items in types.items():
                try:
                    items = sorted(items)
                except TypeError:
                    pass #unorderable type
                yield from items
        types = merge_compatible_types(types)
        return list(gen_from_sorted_comparable_groups(types))

    def _comparable(x, y):
        try:
            x < y
        except TypeError:
            return False
        else:
            return True

    if __name__ == '__main__':    
        print('before py2sort:')
        test = [2, -11.6, 3, 5.0, (1, '5', 3), (object, object()), complex(2, 3), [list, tuple], Fraction(11, 2), '2', type, str, 'foo', object(), 'bar']    
        print(test)
        print('after py2sort:')
        print(py2sort(test))

Whoa

Answer 7

I'd like to recommend starting this sort of task (like imitation of another system's behaviour very close to this one) with detailed clarifying of the target system. How should it work with different corner cases. One of the best ways to do it - write a bunch of tests to ensure correct behaviour. Having such tests gives:

• Better understandind which elements should precede which
• Basic documenting
• Makes system robust against some refactoring and adding functionality. For example if one more rule is added - how to get sure previous are not gets broken?

One can write such test cases:

sort2_test.py

import unittest
from sort2 import sorted2


class TestSortNumbers(unittest.TestCase):
    """
    Verifies numbers are get sorted correctly.
    """

    def test_sort_empty(self):
        self.assertEqual(sorted2([]), [])

    def test_sort_one_element_int(self):
        self.assertEqual(sorted2([1]), [1])

    def test_sort_one_element_real(self):
        self.assertEqual(sorted2([1.0]), [1.0])

    def test_ints(self):
        self.assertEqual(sorted2([1, 2]), [1, 2])

    def test_ints_reverse(self):
        self.assertEqual(sorted2([2, 1]), [1, 2])


class TestSortStrings(unittest.TestCase):
    """
    Verifies numbers are get sorted correctly.
    """

    def test_sort_one_element_str(self):
        self.assertEqual(sorted2(["1.0"]), ["1.0"])


class TestSortIntString(unittest.TestCase):
    """
    Verifies numbers and strings are get sorted correctly.
    """

    def test_string_after_int(self):
        self.assertEqual(sorted2([1, "1"]), [1, "1"])
        self.assertEqual(sorted2([0, "1"]), [0, "1"])
        self.assertEqual(sorted2([-1, "1"]), [-1, "1"])
        self.assertEqual(sorted2(["1", 1]), [1, "1"])
        self.assertEqual(sorted2(["0", 1]), [1, "0"])
        self.assertEqual(sorted2(["-1", 1]), [1, "-1"])


class TestSortIntDict(unittest.TestCase):
    """
    Verifies numbers and dict are get sorted correctly.
    """

    def test_string_after_int(self):
        self.assertEqual(sorted2([1, {1: 2}]), [1, {1: 2}])
        self.assertEqual(sorted2([0, {1: 2}]), [0, {1: 2}])
        self.assertEqual(sorted2([-1, {1: 2}]), [-1, {1: 2}])
        self.assertEqual(sorted2([{1: 2}, 1]), [1, {1: 2}])
        self.assertEqual(sorted2([{1: 2}, 1]), [1, {1: 2}])
        self.assertEqual(sorted2([{1: 2}, 1]), [1, {1: 2}])

Next one may have such sorting function:

sort2.py

from numbers import Real
from decimal import Decimal
from itertools import tee, filterfalse


def sorted2(iterable):
    """

    :param iterable: An iterable (array or alike)
        entity which elements should be sorted.
    :return: List with sorted elements.
    """
    def predicate(x):
        return isinstance(x, (Real, Decimal))

    t1, t2 = tee(iterable)
    numbers = filter(predicate, t1)
    non_numbers = filterfalse(predicate, t2)
    sorted_numbers = sorted(numbers)
    sorted_non_numbers = sorted(non_numbers, key=str)
    return sorted_numbers + sorted_non_numbers

Usage is quite simple and is documented in tests:

>>> from sort2 import sorted2
>>> sorted2([1,2,3, "aaa", {3:5}, [1,2,34], {-8:15}])
[1, 2, 3, [1, 2, 34], 'aaa', {-8: 15}, {3: 5}]

Coptic

Answer 8

To avoid the use of exceptions and going for a type based solution, i came up with this:

#! /usr/bin/python3

import itertools

def p2Sort(x):
    notImpl = type(0j.__gt__(0j))
    it = iter(x)
    first = next(it)
    groups = [[first]]
    types = {type(first):0}
    for item in it:
        item_type = type(item)
        if item_type in types.keys():
            groups[types[item_type]].append(item)
        else:
            types[item_type] = len(types)
            groups.append([item])

    #debuggng
    for group in groups:
        print(group)
        for it in group:
            print(type(it),)
    #

    for i in range(len(groups)):
        if type(groups[i][0].__gt__(groups[i][0])) == notImpl:
            continue
        groups[i] = sorted(groups[i])

    return itertools.chain.from_iterable(group for group in groups)

x = [0j, 'one', 2.3, 'four', -5, 3j, 0j,  -5.5, 13 , 15.3, 'aa', 'zz']
print(list(p2Sort(x)))

Note that an additional dictionary to hold the different types in list and a type holding variable (notImpl) is needed. Further note, that floats and ints aren't mixed here.

Output:

================================================================================
05.04.2017 18:27:57
~/Desktop/sorter.py
--------------------------------------------------------------------------------
[0j, 3j, 0j]
<class 'complex'>
<class 'complex'>
<class 'complex'>
['one', 'four', 'aa', 'zz']
<class 'str'>
<class 'str'>
<class 'str'>
<class 'str'>
[2.3, -5.5, 15.3]
<class 'float'>
<class 'float'>
<class 'float'>
[-5, 13]
<class 'int'>
<class 'int'>
[0j, 3j, 0j, 'aa', 'four', 'one', 'zz', -5.5, 2.3, 15.3, -5, 13]

Postulate

Answer 9

Here is one method of accomplishing this:

lst = [0, 'one', 2.3, 'four', -5]
a=[x for x in lst if type(x) == type(1) or type(x) == type(1.1)] 
b=[y for y in lst if type(y) == type('string')]
a.sort()
b.sort()
c = a+b
print(c)

Buell

Answer 10

@martijn-pieters I don't know if list in python2 also has a __cmp__ to handle comparing list objects or how it was handled in python2.

Anyway, in addition to the @martijn-pieters's answer, I used the following list comparator, so at least it doesn't give different sorted output based on different order of elements in the same input set.

@per_type_cmp(list) def list_cmp(a, b): for a_item, b_item in zip(a, b): if a_item == b_item: continue return python2_sort_key(a_item) < python2_sort_key(b_item) return len(a) < len(b)

So, joining it with original answer by Martijn:

from numbers import Number


# decorator for type to function mapping special cases
def per_type_cmp(type_):
    try:
        mapping = per_type_cmp.mapping
    except AttributeError:
        mapping = per_type_cmp.mapping = {}
    def decorator(cmpfunc):
        mapping[type_] = cmpfunc
        return cmpfunc
    return decorator


class python2_sort_key(object):
    _unhandled_types = {complex}

    def __init__(self, ob):
       self._ob = ob

    def __lt__(self, other):
        _unhandled_types = self._unhandled_types
        self, other = self._ob, other._ob  # we don't care about the wrapper

        # default_3way_compare is used only if direct comparison failed
        try:
            return self < other
        except TypeError:
            pass

        # hooks to implement special casing for types, dict in Py2 has
        # a dedicated __cmp__ method that is gone in Py3 for example.
        for type_, special_cmp in per_type_cmp.mapping.items():
            if isinstance(self, type_) and isinstance(other, type_):
                return special_cmp(self, other)

        # explicitly raise again for types that won't sort in Python 2 either
        if type(self) in _unhandled_types:
            raise TypeError('no ordering relation is defined for {}'.format(
                type(self).__name__))
        if type(other) in _unhandled_types:
            raise TypeError('no ordering relation is defined for {}'.format(
                type(other).__name__))

        # default_3way_compare from Python 2 as Python code
        # same type but no ordering defined, go by id
        if type(self) is type(other):
            return id(self) < id(other)

        # None always comes first
        if self is None:
            return True
        if other is None:
            return False

        # Sort by typename, but numbers are sorted before other types
        self_tname = '' if isinstance(self, Number) else type(self).__name__
        other_tname = '' if isinstance(other, Number) else type(other).__name__

        if self_tname != other_tname:
            return self_tname < other_tname

        # same typename, or both numbers, but different type objects, order
        # by the id of the type object
        return id(type(self)) < id(type(other))


@per_type_cmp(dict)
def dict_cmp(a, b, _s=object()):
    if len(a) != len(b):
        return len(a) < len(b)
    adiff = min((k for k in a if a[k] != b.get(k, _s)), key=python2_sort_key, default=_s)
    if adiff is _s:
        # All keys in a have a matching value in b, so the dicts are equal
        return False
    bdiff = min((k for k in b if b[k] != a.get(k, _s)), key=python2_sort_key)
    if adiff != bdiff:
        return python2_sort_key(adiff) < python2_sort_key(bdiff)
    return python2_sort_key(a[adiff]) < python2_sort_key(b[bdiff])

@per_type_cmp(list)
def list_cmp(a, b):
    for a_item, b_item in zip(a, b):
        if a_item == b_item:
            continue
        return python2_sort_key(a_item) < python2_sort_key(b_item)
    return len(a) < len(b)

PS: It makes more sense to create it as an comment but I didn't have enough reputation to make a comment. So, I'm creating it as an answer instead.

Inhale