编辑代码

public class MergeSort {
    
    // 归并排序算法
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        mergeSortHelper(arr, 0, arr.length - 1);
    }

    private static void mergeSortHelper(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2; // 计算中间位置
        mergeSortHelper(arr, left, mid); // 对左半部分进行归并排序
        mergeSortHelper(arr, mid + 1, right); // 对右半部分进行归并排序
        merge(arr, left, mid, right); // 合并左右两部分
    }

    // 合并两个有序数组
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 创建临时数组
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) { // 依次比较左右两部分的元素
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) { // 将左半部分剩余的元素复制到临时数组
            temp[k++] = arr[i++];
        }
        while (j <= right) { // 将右半部分剩余的元素复制到临时数组
            temp[k++] = arr[j++];
        }
        for (int m = 0; m < temp.length; m++) { // 将临时数组的元素复制回原数组
            arr[left + m] = temp[m];
        }
    }
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
        mergeSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}