Сортировка смежных отличий | Как оптимизировать рекурсивный код

Question

следующий код пытается переставить данный массив таким образом, чтобы отсортировано абсолютное значение различий между соседними элементами. Я придумал решение, использующее рекурсию, и он достаточно эффективен, но я знаю, что это можно сделать таким образом, что это займет меньше времени, но я не уверен, как это сделать.

Код следующее, сделанное в python 3:

def revision(array):
    output = []
    for i in range(len(array)-1):
        dif = abs(array[i]-array[i+1])
        output.append(dif)
    return output

def function(array,output):
    difs = revision(array)

    if len(difs) == 0:
        output.append(array[len(array)-1])
        return 

    v = array[difs.index(min(difs))]
    output.append(v)

    del array[difs.index(min(difs))],difs[difs.index(min(difs))]

    function(array,output)

t = int(input())

for _ in range(t):
    out = []
    n = int(input())
    lista = list(map(int,input().split()))
    lista.sort()
    function(lista,out)
    print(*out)

Если я введу:

2
6
5 -2 4 8 6 5
4
8 1 4 2

Он напечатает правильный ответ:

5 5 4 6 8 -2
1 2 4 8

И с другими делами похож, но, конечно, это занимает все больше и больше времени, и я хочу оптимизировать его. Помогите пожалуйста c: