java怎么实现归并排序

归并排序（merge sort） 是一种比较高效的排序算法，其时间复杂度为O(nlogn)。该算法的基本思想是将要排序的数组分成两个部分，然后分别对这两个部分进行排序，最后将排好序的两个部分合并成一个有序数组。

Java实现归并排序的方法如下：

1. 将要排序的数组从中间分成两部分，分别为左半部分和右半部分；

2. 对左右两个部分分别进行递归排序，直到每个部分只剩下一个元素；

3. 将排好序的左右两个部分合并成一个有序数组，具体实现可以使用两个指针从左到右依次比较两个部分的元素，并按从小到大的顺序放到一个新的数组中；

4. 重复步骤3，直到所有元素都排好序。

具体实现如下：

public class MergeSort {

    public static void mergeSort(int[] arr){
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] temp, int start, int end){
        if(start >= end){
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(arr, temp, start, mid); // 对左半部分进行递归排序
        mergeSort(arr, temp, mid + 1, end); // 对右半部分进行递归排序
        merge(arr, temp, start, mid, end); // 合并已排好序的两个部分
    }

    private static void merge(int[] arr, int[] temp, int start, int mid, int end){
        int i = start;
        int j = mid + 1;
        int 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(int m = start; m <= end; m++){
            arr[m] = temp[m];
        }
    }

    public static void main(String[] args){
        int[] arr = {2, 1, 6, 3, 8, 4, 8, 5, 7};
        mergeSort(arr);
        for(int num : arr){
            System.out.print(num + " ");
        }
    }
}

上述代码中，mergeSort方法是归并排序的入口方法，其中temp数组是用来临时存储有序的元素的。在mergeSort方法中，先将要排序的数组分成两个部分，然后对这两个部分分别进行递归排序，最后将排好序的两个部分合并成一个有序数组。在merge方法中，我们使用两个指针i和j从左到右依次比较左半部分和右半部分的元素，然后将较小的元素放到temp数组中，并移动指针。最后将temp数组的元素复制到原数组中。

运行上述代码，输出结果为：1 2 3 4 5 6 7 8 8。

总结：归并排序是一种稳定的排序算法，能够保证平均时间复杂度为O(nlogn)，但由于需要使用一个额外的数组，因此空间复杂度较高。在Java中实现归并排序，可以通过递归的方式将数组分成两个部分，并用一个临时数组将排好序的两个部分合并。