Найти оптимальный алгоритм сортировки по номерам инверсий/Pearson's r

Question

Можно ли найти оптимальный алгоритм сортировки с заданным числом элементов в предварительно отредактированной последовательности и числом инверсий или числом Pearson's этой последовательности?

Например, у меня есть предварительно отрегулированная последовательность элементов 262143.

Максимальное количество обращений пожертвовано (n(n-1))/2, где n - количество элементов в последовательности (см. here page 2 для этого предположения). Для этого примера максимальным является 34359345153.

Теперь число инверсий моей предварительной последовательности - 1299203725, что составляет 3.78% максимума. Мой Pearson's r - 0.9941. По моему пониманию, это должна быть предварительно упорядоченная последовательность с высокой «сортировкой» (пожалуйста, исправьте меня, если я ошибаюсь).

Я нашел много ссылок на количество инверсий и выражение «Человек» как способ определить «сортировку» последовательности, но я не смог получить какое-то сравнение, для которого количество элементов и инверсий/Pearson's r, сортировка алгоритм является предпочтительным.

Благодарим за помощь.

Answer 1

Вероятно, очень сложно обыграть наихудшее время O (n log n) традиционных алгоритмов сортировки, таких как сортировка слияния, если вы предполагаете, что ваш алгоритм сортировки основан на сравнении. Я считаю, что для того, чтобы сделать так хорошо или лучше, вам, вероятно, придется предположить, что число инверсий равно O (n log n), что намного меньше наихудшего случая O (n^2). Тогда что-то вроде сортировки пузырьков может работать так же быстро, как и O (n), если у вас есть O (n) инверсии, и вы продолжаете обменивать назад, пока элемент образует инверсию со своим левым соседом.