两路合并排序Java

两路合并排序是一种常见的排序算法，它的基本思想是将待排序的数组分成两个子数组，分别进行排序，然后再将两个有序的子数组合并成一个有序的数组。以下是Java实现：

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid); // 对左半部分进行归并排序
        mergeSort(arr, mid + 1, right); // 对右半部分进行归并排序
        merge(arr, left, mid, right); // 合并左右两部分
    }
}

public 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; // i、j分别指向左右两部分的起始位置，k指向temp数组

    while (i <= mid && j <= right) { // 将左右两部分按顺序合并到temp数组中
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) { // 如果左半部分还有剩余元素，将它们全部拷贝到temp数组中
        temp[k++] = arr[i++];
    }

    while (j <= right) { // 如果右半部分还有剩余元素，将它们全部拷贝到temp数组中
        temp[k++] = arr[j++];
    }

    for (i = left, k = 0; i <= right; i++, k++) { // 将排序后的结果拷贝回原数组
        arr[i] = temp[k];
    }
}

在上述代码中，`mergeSort()`方法用于对数组进行归并排序，`merge()`方法用于合并左右两个有序子数组。具体实现过程中，需要使用一个临时数组`temp`来存放排序后的结果。

该算法的时间复杂度为$O(nlogn)$，空间复杂度为$O(n)$。