public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid); // 對(duì)左半部分進(jìn)行遞歸排序
        mergeSort(arr, mid + 1, right); // 對(duì)右半部分進(jìn)行遞歸排序
        merge(arr, left, mid, right); // 合并左右兩個(gè)有序的子數(shù)組
    }
}

public static void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1]; // 臨時(shí)數(shù)組
    int i = left; // 左半部分?jǐn)?shù)組的起始下標(biāo)
    int j = mid + 1; // 右半部分?jǐn)?shù)組的起始下標(biāo)
    int k = 0; // 臨時(shí)數(shù)組的起始下標(biāo)
    // 將左右兩個(gè)有序的子數(shù)組合并為一個(gè)有序的數(shù)組
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    // 將左半部分的剩余元素復(fù)制到臨時(shí)數(shù)組中
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    // 將右半部分的剩余元素復(fù)制到臨時(shí)數(shù)組中
    while (j <= right) {
        tmp[k++] = arr[j++];
    }
    // 將臨時(shí)數(shù)組中的元素復(fù)制回原數(shù)組中
    for (int x = 0; x < k; x++) {
        arr[left + x] = tmp[x];
    }
}

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid); // 對(duì)左半部分進(jìn)行遞歸排序
            mergeSort(arr, mid + 1, right); // 對(duì)右半部分進(jìn)行遞歸排序
            merge(arr, left, mid, right); // 合并左右兩個(gè)有序的子數(shù)組
        }
    }
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1]; // 臨時(shí)數(shù)組
        int i = left; // 左半部分?jǐn)?shù)組的起始下標(biāo)
        int j = mid + 1; // 右半部分?jǐn)?shù)組的起始下標(biāo)
        int k = 0; // 臨時(shí)數(shù)組的起始下標(biāo)
        // 將左右兩個(gè)有序的子數(shù)組合并為一個(gè)有序的數(shù)組
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        // 將左半部分的剩余元素復(fù)制到臨時(shí)數(shù)組中
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        // 將右半部分的剩余元素復(fù)制到臨時(shí)數(shù)組中
        while (j <= right) {
            tmp[k++] = arr[j++];
        }
        // 將臨時(shí)數(shù)組中的元素復(fù)制回原數(shù)組中
        for (int x = 0; x < k; x++) {
            arr[left + x] = tmp[x];
        }
    }
    public static void main(String[] args) {
        int[] arr = {5, 3, 9, 1, 7, 2, 8, 4, 6};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}