参考资料

水平有限，欢迎交流！
【如何优雅地排序——3分钟看懂【归并排序】的基本思想】

练习题

P1177 【模板】排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

关键步骤与应用

步骤

在归并过程中，主要包含两个关键步骤：

1. 分割（Divide）：将数组递归地分成两个或多个子数组。
2. 合并（Merge）：将两个或多个已排序的子数组合并成一个有序的大数组。

应用

可用于求逆序对的对数（力扣LCR 170）

归并排序

P1177 【模板】排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static int N;
    static int[] arr;
    static int[] tmp;
    //分割
    static void MergeSort(int[] a, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) >> 1;
        MergeSort(a, l, mid);
        MergeSort(a, mid + 1, r);
        merge(a, l, mid, r);
    }
    //合并
    static void merge(int[] a, int l, int mid, int r) {
        int i = l, j = mid + 1, k = 0;

        // 合并两个已排序的子数组
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
            }
        }

        // 处理剩余的元素
        while (i <= mid) {
            tmp[k++] = a[i++];
        }

        // 将临时数组中的元素复制回原数组
        for (int x = 0; x < k; x++) {
            a[l+x] = tmp[x];
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(in.readLine());
        arr = new int[N];
        tmp = new int[N];
        String[]line = in.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }
        MergeSort(arr, 0, N - 1);
        for (int i : arr) {
            out.write(i + " ");
        }
        out.flush();
        in.close();
        out.close();
    }
}

求逆序对对数（仅考虑思路，不考虑消耗）

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

class Solution {
    int []tmp;
    int mergeSort(int []nums,int l,int r){
        if(l>=r)
            return 0;
        int cnt = 0;
        int mid = l +r >>1;
        cnt+=mergeSort(nums, l, mid);
        cnt+=mergeSort(nums, mid+1, r);
        int i = l,j = mid +1 ,k = 0;
        while(i<=mid&&j<=r){
            if(nums[i]<=nums[j]){
                tmp[k++] = nums[i++];
            }
            else{
                cnt+=(mid-i+1);
                tmp[k++] = nums[j++];
            }
        }
        while(i<=mid){
            tmp[k++] = nums[i++];
        }
        for(int x = 0;x<k;x++){
            nums[x+l] = tmp[x];
        }
        return cnt;
    }
    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        return mergeSort(record, 0, record.length-1);
    }
}

3193. 统计逆序对的数目 - 力扣（LeetCode）
下面为暴力写法，过一半左右

import java.util.ArrayList;
import java.util.List;

class Solution {
    final int mod = 1000000007;
    List<List<Integer>> ans;
    int[] tmp;
    boolean[] vis;

    // 调整mergeSort方法以正确计算逆序对
    int mergeSortAndCount(List<Integer> cur, int l, int r) {
        if (l >= r) return 0;
        int mid = (l + r) >> 1;
        int count = 0;
        count += mergeSortAndCount(cur, l, mid);
        count += mergeSortAndCount(cur, mid + 1, r);
        count += mergeAndCount(cur, l, mid, r);
        return count;
    }

    int mergeAndCount(List<Integer> cur, int l, int mid, int r) {
        int i = l, j = mid + 1, k = 0;
        int count = 0;
        while (i <= mid && j <= r) {
            if (cur.get(i) <= cur.get(j)) {
                tmp[k++] = cur.get(i++);
            } else {
                tmp[k++] = cur.get(j++);
                count += (mid - i + 1);  // 确定逆序对的个数
            }
        }
        while (i <= mid) {
            tmp[k++] = cur.get(i++);
        }
        for (i = 0; i < k; i++) {
            cur.set(l + i, tmp[i]);
        }
        return count;
    }

    void dfs(int[] nums, List<Integer> res, int[][] requirements) {
        int len = nums.length;
        if (res.size() == len) {
            // 判断所有的要求是否都满足
            boolean isValid = true;
            for (int[] req : requirements) {
                int end = req[0];
                int cnt = req[1];
                List<Integer> sublist = new ArrayList<>(res.subList(0, end + 1));
                tmp = new int[sublist.size()];
                int inversionCount = mergeSortAndCount(sublist, 0, end);
                if (inversionCount != cnt) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                ans.add(new ArrayList<>(res)); // 只有满足所有要求时才添加到结果集
            }
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!vis[i]) {
                vis[i] = true;
                res.add(nums[i]);
                dfs(nums, res, requirements);
                res.remove(res.size() - 1);
                vis[i] = false;
            }
        }
    }

    public int numberOfPermutations(int n, int[][] requirements) {
        ans = new ArrayList<>();
        int[] nums = new int[n];
        for (int j = 0; j < n; j++) {
            nums[j] = j;
        }
        vis = new boolean[n];
        dfs(nums, new ArrayList<>(), requirements);

        return ans.size() % mod;
    }
}