算法之逆序对

private static int count;

private static void merge(int[] arr, int startIndex, int midIndex, int endIndex) {
    /**
     * 合并策略: 
     * 1. 新建两个数组，分别存取左半部分排好序的数组和右半部分排好序的数组
     * 2. 分别从左右两个数组最开始下标开始遍历，选取较小的依次放入原数组对应位置
     * 3. 最终如果左右数组中有一个已经遍历完成，另一个数组所剩的元素直接放入元素组后面部分即可
     */
    // STEP1
    int[] leftArr = new int[midIndex - startIndex];
    int[] rightArr = new int[endIndex - midIndex];
    System.arraycopy(arr, startIndex, leftArr, 0, leftArr.length);
    System.arraycopy(arr, midIndex, rightArr, 0, rightArr.length);
    
    // STEP2
    int k = startIndex; // 存储原数组中的下标
    int i = 0;          // 存储左边数组的下标
    int j = 0;          // 存储右边数组的下标
    while (i < leftArr.length && j < rightArr.length) {
        // 将较小的元素复制到元素组对应下标k，并且移动较小元素所在数组下标
        if (leftArr[i] < rightArr[j]) {
            arr[k++] = leftArr[i++];    
        } else {
            // 此时说明 arr[i]到arr[leftArr.length - 1]的值都比arr[j]大，即此时以arr[j]结尾的逆序对个数为: 
            count += leftArr.length - i;
            arr[k++] = rightArr[j++];
        }
    }
    
    // STEP3
    if (i < leftArr.length) {
        System.arraycopy(leftArr, i, arr, k, leftArr.length - i);
    } else if (j <= rightArr.length) {
        System.arraycopy(rightArr, j, arr, k, rightArr.length - j);
    }
}