How to code this "strange" sort in Python

Question

I would like to write a function which performs efficiently this "strange" sort (I am sorry for this pseudocode, it seems to me to be the clearest way to introduce the problem):

l=[[A,B,C,...]]
while some list in l is not sorted (increasingly) do
  find a non-sorted list (say A) in l
  find the first two non-sorted elements of A (i.e. A=[...,b,a,...] with b>a)
  l=[[...,a,b,...],[...,b+a,...],B,C,...]

Two important things should be mentioned:

1. The sorting is dependent on the choice of the first two non-sorted elements: if A=[...,b,a,r,...], r<a<b and we choose to sort wrt to (a,r) then the final result won't be the same. This is why we fix the two first non-sorted elements of A.
2. Sorting this way always comes to an end.

An example:

In: Sort([[4,5,3,10]])
Out: [[3,4,5,10],[5,7,10],[10,12],[22],[4,8,10]]

since

(a,b)=(5,3): [4,5,3,10]->[[4,3,5,10],[4,8,10]]
(a,b)=(4,3): [[4,3,5,10],[4,8,10]]->[[3,4,5,10],[7,5,10],[4,8,10]]
(a,b)=(7,5): [[3,4,5,10],[7,5,10],[4,8,10]]->[[3,4,5,10],[5,7,10],[12,10],[4,8,10]]
(a,b)=(12,10): [[3,4,5,10],[5,7,10],[12,10],[4,8,10]]->[[3,4,5,10],[5,7,10],[10,12],[22],[4,8,10]] 

Thank you for your help!

EDIT

Why am I considering this problem: I am trying to do some computations with the Universal Enveloping Algebra of a Lie algebra. This is a mathematical object generated by products of some generators x_1,...x_n. We have a nice description of a generating set (it amounts to the ordered lists in the question), but when exchanging two generators, we need to take into account the commutator of these two elements (this is the sum of the elements in the question). I haven't given a solution to this question because it would be close to the worst one you can think of. I would like to know how you would implement this in a good way, so that it is pythonic and fast. I am not asking for a complete solution, only some clues. I am willing to solve it by myself .

Answer 1

def s_sort(n):
    new_lst = []
    while len(n) > 0:
        new_lst.append(min(n))
        n.remove(min(n))
        if len(n) > 0:
            new_lst.append(max(n))
            n.remove(max(n))
    return new_lst

n = eval(input())
print(s_sort(n))

Answer 2

Here's a simple implementation that could use some improvement:

def strange_sort(lists_to_sort):
    # reverse so pop and append can be used
    lists_to_sort = lists_to_sort[::-1]
    sorted_list_of_lists = []
    while lists_to_sort:
        l = lists_to_sort.pop()
        i = 0
        # l[:i] is sorted
        while i < len(l) - 1:
            if l[i] > l[i + 1]:
                # add list with element sum to stack
                lists_to_sort.append(l[:i] + [l[i] + l[i + 1]] + l[i + 2:])
                # reverse elements
                l[i], l[i + 1] = l[i + 1], l[i]
                # go back if necessary
                if i > 0 and l[i - 1] > l [i]:
                    i -= 1
                    continue
            # move on to next index
            i += 1
        # done sorting list
        sorted_list_of_lists.append(l)
    return sorted_list_of_lists

print(strange_sort([[4,5,3,10]]))

This keeps track of which lists are left to sort by using a stack. The time complexity is pretty good, but I don't think it's ideal

Answer 3

Firstly you would have to implement a while loop which would check if all of the numbers inside of the lists are sorted. I will be using all which checks if all the objects inside a sequence are True.

def a_sorting_function_of_some_sort(list_to_sort):
    while not all([all([number <= numbers_list[numbers_list.index(number) + 1] for number in numbers_list 
                        if not number == numbers_list[-1]]) 
                   for numbers_list in list_to_sort]):

        for numbers_list in list_to_sort:

            # There's nothing to do if the list contains just one number
            if len(numbers_list) > 1:
                for number in numbers_list:
                    number_index = numbers_list.index(number)
                    try:
                        next_number_index = number_index + 1
                        next_number = numbers_list[next_number_index]
                    # If IndexError is raised here, it means we don't have any other numbers to check against,
                    # so we break this numbers iteration to go to the next list iteration
                    except IndexError:
                        break
                    if not number < next_number:
                        numbers_list_index = list_to_sort.index(numbers_list)
                        list_to_sort.insert(numbers_list_index + 1, [*numbers_list[:number_index], number + next_number, 
                                                                     *numbers_list[next_number_index + 1:]])
                        numbers_list[number_index] = next_number
                        numbers_list[next_number_index] = number
                        # We also need to break after parsing unsorted numbers
                        break
    return list_to_sort