Python has a built-in sorted function, you should use it. What it needs to sort according to some special criteria is a key function:
def max_digit_diff(n):
n_str = str(n)
return int(max(n_str)) - int(min(n_str))
This uses the fact that "0" < "1" < ... < "9".
However, the sorted function uses a stable sorting algorithm, so if two elements compare equal, the original order is preserved. But here we want the opposite order (later elements come first), so we just reverse the list first:
def digit_difference_sort(a):
return sorted(reversed(a), key=max_digit_diff)
This should be vastly easier to read than your convoluted function. Note that the function names also follow Python's official style-guide, PEP8.
Like all (good) sorting functions, this is \$\mathcal{O}(n \log n)\$. Here is a timing comparison to your function with arrays up to length 10k (at which point your function takes more than a minute...).
Here is an implementation of the radix sort suggested by @JollyJoker in their answer:
from itertools import chain
def radix_sort(a):
sub_a = [[] for _ in range(10)]
for x in a:
sub_a[max_digit_diff(x)].append(x)
return list(chain.from_iterable(reversed(x) for x in sub_a))
This seems to have the same complexity as my approach, probably the implementation of max_digit_diff actually dominates this:
