无序数组的两路合并排序java

以下是一个简单的 Java 实现：

public static void mergeSort(int[] arr, int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

public static void merge(int[] arr, int start, int mid, int end) {
    int[] temp = new int[arr.length];
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= end) {
        temp[k++] = arr[j++];
    }
    for (i = start; i <= end; i++) {
        arr[i] = temp[i];
    }
}

在 `mergeSort` 方法中，我们首先找到数组的中间位置 `mid`，然后递归地对数组的左半部分（即 `start` 到 `mid`）和右半部分（即 `mid + 1` 到 `end`）进行归并排序。最后，我们调用 `merge` 方法将左半部分和右半部分合并成一个有序数组。

在 `merge` 方法中，我们创建一个临时数组 `temp`，然后使用三个指针 `i`、`j` 和 `k` 分别指向左半部分、右半部分和临时数组中的下一个位置。我们比较 `arr[i]` 和 `arr[j]` 的大小，将较小的元素放入临时数组中，并将相应的指针向后移动。重复这个过程，直到其中一个指针到达了数组的末尾。然后我们将另一个指针所指的元素依次放入临时数组中，并将指针向后移动。最后，我们将临时数组中的元素复制回原始数组中。