Минимальное количество специальных ходов для сортировки числа

Одно из возможных решений — найти самую длинную возрастающую подпоследовательность и переместить только те элементы, которые не входят в нее.

Я не могу доказать, что это оптимально, но легко доказать, что это правильно и лучше, чем N свопов.

Вот доказательство концепции в Python 2. Я реализовал его как алгоритм O(n²), но я почти уверен, что его можно сократить до O(n log n).

from operator import itemgetter

def LIS(V):
    T = [1]*(len(V))
    P = [-1]*(len(V))

    for i, v in enumerate(V):
        for j in xrange(i-1, -1, -1):
            if T[j]+1 > T[i] and V[j] <= V[i]:
                T[i] = T[j] + 1
                P[i] = j

    i, _ = max(enumerate(T), key=itemgetter(1))
    while i != -1:
        yield i
        i = P[i]

def complement(L, n):
    for a, b in zip(L, L[1:]+[n]):
        for i in range(a+1, b):
            yield i

def find_moves(V):
    n = len(V)
    L = list(LIS(V))[::-1]
    SV = sorted(range(n), key=lambda i:V[i])
    moves = [(x, SV.index(x)) for x in complement(L, n)]

    while len(moves):
        a, b = moves.pop()
        yield a, b
        moves = [(x-(x>a)+(x>b), y) for x, y in moves]


def make_and_print_moves(V):
    print 'Initial array:', V

    for a, b in find_moves(V):
        x = V.pop(a)
        V.insert(b, x)        
        print 'Move {} to {}. Result: {}'.format(a, b, V)
    print '***'

make_and_print_moves([1, 15, 2, 5, 10])

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

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

Выводит что-то вроде:

Initial array: [1, 15, 2, 5, 10]
Move 1 to 4. Result: [1, 2, 5, 10, 15]
***
Initial array: [4, 3, 2, 1]
Move 3 to 0. Result: [1, 4, 3, 2]
Move 3 to 1. Result: [1, 2, 4, 3]
Move 3 to 2. Result: [1, 2, 3, 4]
***
Initial array: [1, 2, 4, 3]
Move 3 to 2. Result: [1, 2, 3, 4]
***