merge sort java

归并排序（Merge Sort）是一种分治算法，常用于 Java 中进行数组或列表的排序。它的基本思想是将待排序的序列不断地分成两个子序列，直到每个子序列只有一个元素，然后合并这两个有序的子序列，形成一个新的有序序列。以下是使用 Java 实现归并排序的一个简单版本：

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);
            mergeSort(arr, mid + 1, right);

            // 合并两个已排序的部分
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 创建临时数组存储两个部分
        int[] temp = new int[n1 + n2];
        
        // 指针，分别指向左右两个部分的起始位置
        int i = 0, j = 0, k = left;

        // 将较小的元素依次放入原数组
        while (i < n1 && j < n2) {
            if (arr[left + i] <= arr[mid + j]) {
                temp[k++] = arr[left + i++];
            } else {
                temp[k++] = arr[mid + j++];
            }
        }

        // 如果左边还有剩余元素，直接复制过去
        while (i < n1) {
            temp[k++] = arr[left + i++];
        }

        // 同理，如果右边还有剩余元素
        while (j < n2) {
            temp[k++] = arr[mid + j++];
        }

        // 把临时数组的内容复制回原数组
        for (int x = 0; x < n1 + n2; x++) {
            arr[k++] = temp[x];
        }
    }

    // 测试方法
    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10};
        mergeSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

上述代码首先定义了 `mergeSort` 函数，负责递归分割数组和调用 `merge` 函数来合并。`merge` 函数则是合并两个已排序的区间。在主函数 `main` 中，创建了一个整数数组，调用 `mergeSort` 对其进行了排序，并打印出结果。