Изменения

Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. После этого легко можно восстановить массив <tex> A_{S_e} </tex>:

M = []

M.add(Pair(S[<tex> A_{S_o}</tex>[i] - 1], <tex> A_{S_o}</tex>[i]))

quick_stable_sort(M)