我正在开发一个改进的版本，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
这有意义吗？
最终，我必须进行倒数计数，直到算法终止。有人可以就这个问题给我一个提示吗？
（直观地说，当合并完成时算法终止时，我会计算合并部分。）
干杯，安德鲁