Упорядочить ряд чисел методом случайного выбора пары чисел

Это вопрос не мой, а какого-то человека с dxdy, поэтому проверку решения я сделать не смогу, но мне лично самому стала интересна данная задача.

Пользователь вводит перестановку длины N (в данном случае не более 10). Вы должны упорядочить ее по возрастанию.

Вам доступна только следующая операция: выбрать два различных случайных числа и, если правое меньше левого, поменять их местами.

Какое мат. ожидание количества операций, необходимых для упорядочивания введенного ряда?

В изначальном вопросе требовалось, чтобы в тестирующей системе (доступа к которой у нас, к сожалению, нет) программа отрабатывала на 40 рядах за три секунды, поэтому необходимо найти решение, имеющее вычислительную сложность меньшую, чем O(n!), или ее же, но с очень малой константой.

Пример:

Input:
4
1 3 2 4
_______
Output:
6.0
_______
Пояснение:
F(1324) = 5/6 * (F(1324) + 1) + 1/6 * (F(1234) + 1)
F(1234) = 0, так как уже является требуемой перестановкой