8.5 归并排序、基数排序·综合题讲评

逆序对可在归并中计数：右项先于左项取出时，贡献左半剩余元素数。

手工推演与代码

[3,1,2]合并时1先于3贡献1，2先于3再贡献1，共2。

代码实现必须保持当前有序区、堆区或归并段的不变量，并对空数组、单元素、重复键和逆序输入测试。

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。每发现一次跨区逆序只加1；相等也计逆序。

迁移训练

[4,3,2,1]逆序对数答案6，归并计数O(nlogn)。