mergesort（逆序数怎么算？）

　　逆序数与归并排序：一个有趣的交织

　　嗨，大家好!我是一名资深的操作系统优化师，今天我想和大家聊一聊关于逆序数和归并排序的有趣故事。

　　首先，让我们来了解一下逆序数是什么。逆序数是指在一个排列中，如果前面的数比后面的数大，那么这两个数就被称为一个逆序。比如说，对于序列 {2,4,3,1}，逆序分别是 (2,1)、(4,3)、(4,1)和(3,1)，所以这个序列的逆序数为4。

　　刚刚给大家展示了一个用Visual Basic 6.0编写的例子，它使用的是直接计数的方法。这个例子会逐个枚举逆序并统计个数。虽然这种方法很简单明了，但是时间复杂度是O(n²)，所以对于大规模的排列来说，效率可能不够理想。

　　那么有没有一种更快的计算方法呢?答案是肯定的!我们可以在归并排序的同时计算逆序数。接下来，我会用一个C++编写的例子来演示这种方法。

　　首先，我们会定义两个数组，is1和is2。is1就是我们的原始数组，is2是一个临时数组。还有一个变量n，表示你自己定义的数组长度。

　　我们要用merge函数来进行归并排序和逆序数的计算。这个函数会返回逆序数的数量。它接受三个参数：low、mid和high，分别表示数组的起始位置、中间位置和结束位置。

　　在merge函数中，我们使用了一个while循环来比较is1数组中的元素，并将它们按照大小顺序放入is2数组中。这个循环中，我们还用了一个count变量来记录逆序数的数量。每当后段的数组元素比前段的数组元素提前时，我们就记录这个提前的距离。

　　当循环结束后，我们要将is2数组中排好序的元素写回到is1数组中。

　　接下来，我们来看一下mergeSort函数。它也接受两个参数：a和b，表示排序的范围。在函数中，我们首先判断a是否小于b，如果是的话，我们就计算出中间位置mid，并用递归的方式调用mergeSort函数。

　　在递归调用的过程中，我们不断将问题拆分成更小的子问题，并将子问题的解累加到count变量中。

　　最后，我们将count的值返回给调用者。

　　通过这种巧妙的方法，在归并排序的过程中计算逆序数，我们可以大大提高计算的效率。