How to sort liberally-deep list of lists and integers?

Question

Let's say I have a list like that:

[[5, [2, 1], 3], [3, [8, 7], [2, 1, 3], 2], [[3, 2, 1], 3, -1]]

(each list can store unspecified number of integers and lists in any order). Rules for sorting:

• integers (if any) should be before any list
• integers are sorted normally (from lower to higher value)
• list is "smaller" than another when the first element is lower, if the same we consider the second element, the third, and so on.
• If the list has the same values as another but less, it's smaller. [1, 2] < [1, 2, 3]

So the final result should be:

[[-1, 3, [1, 2, 3]], [2, 3, [1, 2, 3], [7, 8]], [3, 5, [1, 2]], ]

How to implement that kind of sorting? I've tried to pass recursive function as sort key in sorted, but mostly ended with TypeError (< not supported for int and list).

Another example:

[1, 4, 3, [[5, 7, 1, 2], 2, 5, 10, 2], 8, [2, 5, [5, 3, 3]], [2, 5, 10, 2, [1, 2, 5]]]

After sorting :

[1, 3, 4, 8, [2, 2, 5, 10, [1, 2, 5]], [2, 2, 5, 10, [1, 2, 5, 7]], [2, 5, [3, 3, 5]]]

Answer 1

One way to compare sibling structures (i.e., deeply nested values inside the same list) correctly, safely and efficiently, is to decorate everything and keep it decorated until all the sorting is done. Then undecorate everything at the end. This doesn't modify the given structure but builds a sorted new one:

def deepsorted(x):
    def decosorted(x):
        if isinstance(x, int):
            return 0, x
        return 1, sorted(map(decosorted, x))
    def undecorated(x):
        islist, x = x
        if islist:
            return list(map(undecorated, x))
        return x
    return undecorated(decosorted(x))

Another way is to not rely on natural comparisons but use an old-style cmp function instead. This sorts in-place:

from functools import cmp_to_key

def deepsort(x):
    def cmp(a, b):
        if isinstance(a, int):
            if isinstance(b, int):
                return a - b
            return -1
        if isinstance(b, int):
            return 1
        diffs = filter(None, map(cmp, a, b))
        return next(diffs, len(a) - len(b))
    key = cmp_to_key(cmp)
    def sort(x):
        if isinstance(x, list):
            for y in x:
                sort(y)
            x.sort(key=key)
    sort(x)

Testing code (Try it online!):

from copy import deepcopy

tests = [
    ([[5, [2, 1], 3], [3, [8, 7], [2, 1, 3], 2], [[3, 2, 1], 3, -1]],
     [[-1, 3, [1, 2, 3]], [2, 3, [1, 2, 3], [7, 8]], [3, 5, [1, 2]], ]),

    ([1, 4, 3, [[5, 7, 1, 2], 2, 5, 10, 2], 8, [2, 5, [5, 3, 3]], [2, 5, 10, 2, [1, 2, 5]]],
     [1, 3, 4, 8, [2, 2, 5, 10, [1, 2, 5]], [2, 2, 5, 10, [1, 2, 5, 7]], [2, 5, [3, 3, 5]]]),

    ([[1, 2], [1, [2]]],
     [[1, 2], [1, [2]]]),

    ([[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]],
     [[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]),

    ([[[1, 2]], [[1, [2]]]],
     [[[1, 2]], [[1, [2]]]]),

    ([[[1, [2]]], [[1, 2]]],
     [[[1, 2]], [[1, [2]]]]),

    ([[1, 3], [1, 2]],
     [[1, 2], [1, 3]]),
]

for given, wanted in tests:
    copy = deepcopy(given)
    deepsort(copy)
    print(deepsorted(given) == wanted,
          copy == wanted)