小蓝有一个长度为 nn 的数组, 初始时从左到右依次是 1,2,3, \ldots n1,2,3,…n 。

小蓝想要对这个数组进行一些操作，使得最终数组的逆序对数目最小。逆序对指的是在数组中，若 i<j 但 a[i]>a[j]，则称 (i,j) 是一个逆序对。

要求：请你给出一个算法，使得操作后的数组逆序对数目最小。并且，给出算法的时间复杂度和空间复杂度，并说明你的算法为什么能保证得到最小的逆序对数目。

思路：这个问题可以直接用归并排序的思想来解决。归并排序的过程中，将两个已经排序的数组合并成一个有序数组的时候需要记录逆序对的数目。具体实现的过程中，可以在合并数组的过程中记录左边数组中大于右边数组中当前元素的个数，从而求出逆序对的数目。

时间复杂度：归并排序的时间复杂度为 O(nlogn)，只需要在合并数组的时候顺便统计逆序对的数目，时间复杂度不变。

空间复杂度：归并排序的空间复杂度为 O(n)，需要一个额外的数组来存储排序后的结果。

正确性证明：算法的正确性可以用数学归纳法来证明。假设对于长度为 k 的数组能够得到最小的逆序对数目，现在考虑长度为 k+1 的数组。将数组分为左右两个部分，分别排序并统计出左半边有 m 个元素大于右半边的元素，那么左半边中的逆序对数目为 x，右半边中的逆序对数目为 y，则新的逆序对数目为 x+y+m。可以发现，对于左右两半边来说，当前的排序顺序是最小的，因此如果左右两半边中的元素之间存在逆序对，一定是由左半边中的元素和右半边的元素组成的。因此，对于 m，只需要找出左半边中第 m+1 个元素和右半边的元素进行比较，如果左半边的元素比右半边的元素大，逆序对数目可以减少 m，如果左半边的元素比右半边的元素小，则逆序对数目会增加左半边中比这个元素小的元素的个数，即 x+m+1，这样可以保证每次合并数组时逆序对数目最小。