algorithm - Find the optimal sorting algorithm by inversions number/Pearson's r

Question

is it possible to find a optimal sorting algorithm with a given number of elements in a presorted sequence and a inversions number or a Pearson's r of that sequence?

For example I have a presorted sequence of 262143 elements.

The maximum amount of inversions is donated by (n(n-1))/2 where n is the number of elements in the sequence (see here page 2 for this assumption). For this example the maximum is therefor 34359345153.

Now the number of inversions of my presorted sequence is 1299203725 which is 3.78% of the maximum. My Pearson's r is 0.9941. By my understanding this should be a presorted sequence with a high "sortedness" (Please correct my if I'm wrong).

I found many references to the number of inversions and the Person's r as a way to define the "sortedness" of a sequence but I could not get some kind of comparison for which number of elements and inversions/Pearson's r which sorting algorithm is the preferred one.

Thanks for your help.

Answer 1

如果您假设您的排序算法是基于比较的，那么可能很难击败传统排序算法（如合并排序）的最坏情况 O(n log n) 时间。我相信为了做得更好或更好，您可能不得不假设反转次数为 O(n log n)，远小于最坏情况的 O(n^2)。然后，如果您有 O(n) 次反转，并且只要一个元素与其左邻居形成反转，您就可以继续向后交换，那么像冒泡排序这样的东西可以在 O(n) 时间内运行。