分治法统计逆序对必须用归并排序，因其天然维护左右子区间有序性与位置关系，可在合并时批量识别跨区逆序；快排和堆排不保序、无法自然捕获跨区间逆序关系。
直接用数组实现分治算法解决逆序对统计，关键不在“数组”本身，而在于如何在归并排序的合并阶段，借助两个已有序子数组的结构特性，边排序边计数。暴力法 O(n²) 容易写但不可扩展；分治法把时间压到 O(n log n)，核心就落在“合并时怎么数”这一步。
为什么必须用归并，而不是快排或堆排
快排和堆排不保序、不显式维护左右子区间之间的位置关系，无法自然捕获“左半段某个数 > 右半段某个数”这类跨区间逆序。而归并排序天然把原数组递归拆成左右两半，且每次合并前，左右两段各自有序——这个前提让跨区逆序对能被批量识别。
例如：left = [5, 7, 9]，right = [4, 5, 8]，当 left[0]=5 > right[0]=4 时，说明 left[0] 比 right 中从下标 0 开始的所有更小元素都大。由于 right 有序，只要找到 right 中第一个 ≥5 的位置，就能算出 left[0] 贡献了多少个逆序对。
合并过程中实时统计的两种等效方式
实际编码中常用的是“右移右指针法”，逻辑清晰、不易错：
- 设 left[i] 和 right[j] 当前待比，若 left[i] ≤ right[j]，说明 left[i] 不构成跨区逆序，直接取 left[i] 放入临时数组，i++
- 若 left[i] > right[j]，说明 left[i] 比 right[j] 及 right 中所有 j 后面的元素都大（因 right 有序），那么 left[i] 就贡献了 (right_len − j) 个逆序对
- 此时取 right[j] 入临时数组，j++，继续比较 left[i] 和下一个 right 元素
注意：只在取 right 元素时累加计数，因为此时确认 left[i] 确实大于当前及后续所有未处理的 right 元素。
数组操作细节与常见坑点
用原数组+辅助数组配合实现，避免覆盖：
- 递归调用时传入原数组的左右边界，如 sort(arr, l, r, tmp)，不是传子数组副本，节省空间
- 合并时把结果暂存到 tmp[l..r]，再一次性拷回 arr[l..r]，防止边合并边改原数组导致逻辑错乱
- 递归终止条件是 l ≥ r（单个或空元素），不是 l == r−1；否则长度为 2 的数组会漏处理
- mid 计算推荐用 l + (r − l) / 2，防整型溢出，尤其在大索引场景下
完整逻辑链条不能断环
逆序对总数 = 左半段内部逆序对 + 右半段内部逆序对 + 跨左右的逆序对。三者必须全统计：
- 前两项靠递归调用自身完成
- 第三项靠合并过程实时累计
- 每次 merge 返回前，把本次跨区计数加到总结果里
漏掉任意一项，结果必错。比如数组 [1,3,2,4]，跨区部分只有 (3,2)，但若没递归统计左右内部，就会少算 0（左右各单元素，无内部逆序），结果正确；而 [3,2,1] 拆成 [3,2] 和 [1]，左半段 [3,2] 内部已有 1 个逆序，必须靠递归返回值带上来。
