细化合并-排序以计算反转的数量

Question

我正在开发一个改进版本的merge sort，这样它就可以counts the number of inversions了。

注意:我不想让你完成我的作业，但我对此有一些想法，我很想知道它们是否有意义。

因为合并排序是O(nlogn的，所以我需要在不影响其整体性能的情况下对其进行调整。我想我必须插入一个花费恒定时间的测试(1)

(1)我用A[i] > A[j] given that i<j测试反转(上)

为了找到合适的位置来插入测试，我问自己：when during the execution of merge sort is guaranteed that the test runs unrelated to n?

我认为唯一正确的地方是当the list is split into one-element lists

因此，我将提出以下算法调整

use divide-and-conquer and split the list to one elements lists
test A[i] > A[j] as i<j is true for two adjacent lists 

这有什么意义吗？

最终，我必须进行倒置计数，直到算法终止。关于这个问题，有人能给我一个提示吗？

(直观地说，当合并完成时算法终止时，我会将计数提供给合并部分。)

干杯，安德鲁

Answer 1

如果只在数组大小为1时计数，则只会看到成对的反转。我认为你只想在所有的递归调用中保持一个计数器，并在合并步骤中，将左子数组中的元素与右子数组中的元素进行比较，并且右边的元素更小(假设你是按升序排序)。