题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。例如，在数组 {7, 5, 6, 4} 中，一共存在 5 个逆序对，分别是 (7, 6)、(7, 5)、(7, 4)、(6, 4) 和 (5, 4)。
思路 1：穷举
最直接的思路是：遍历数组中的每一个数字，遍历到一个数字时，扫描其后的所有数字，逐个比较大小，记录逆序对数目。这样的做法，需要遍历 n 个数字，然后对其后的 O(n) 个数字再遍历，因此需要 $O(n^2)$ 的时间复杂度。我们需要思考更快的算法。
思路 2：归并排序
思路 1 由于需要对 n 个数字其后的 O(n) 个数字再遍历，导致较低的时间效率。我们能不能想到一种算法不对其后的所有数字进行遍历呢？办法就是排序，更确切一点是归并排序。归并排序的过程与计算逆序对的过程完全一致，只需要在归并的过程中记录一下逆序对数即可。整个过程我不详细描述。这个算法的时间复杂度是 $O(n\,log\,n)$；需要一个临时数组拷贝整个输入数组，空间复杂度为 O(n)。