Java归并排序（Merge Sort）

归并排序（Merge Sort）是建立在归并操作上的一种有效的稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并排序将两个有序的子序列合并得到一个完全有序的序列，即先使每个子序列有序，再使子序列段间有序。若将两个有序的列表合并成一个有序的列表，我们称之为二路归并。

归并排序的速度仅次于快速排序，时间复杂度为O(nlogn)。其拆分过程中使用了二分思想，是一个递归的过程，为了减少在递归过程中不断开辟空间的问题，我们可以在归并排序之前，先开辟出一个临时空间，在递归过程中统一使用此空间进行归并即可。

例如：

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{86,23,7,45,19,10};
        int left = 0;
        int right = arr.length-1;
        int[] tem = Arrays.copyOf(arr,arr.length);
        print(arr);
        mergeSort(arr,left,right,tem);
        print(arr);
    }
    public static void mergeSort(int[] arr,int left,int right,int[] tem) {
        if(right-left<1) {
            return;
        }
        int mid = left + (right-left)/2;
        mergeSort(arr,left,mid,tem);
        mergeSort(arr,mid+1,right,tem);
        merge(arr,left,mid,right,tem);
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] tem) {
        int index = 0;
        int l = left,r = mid+1;
        while(l <= mid && r <= right) {
            if(arr[l]<arr[r]) {
                tem[index++] = arr[l++];
            }else{
                tem[index++] = arr[r++];
            }
        }
        while(l <= mid) {
            tem[index++] = arr[l++];
        }
        while(r <= right) {
            tem[index++] = arr[r++];
        }
        for(int i=0;i<(right-left+1);i++) {
            arr[left+i] = tem[i];
        }
    }
    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
    }
}

运行结果如下：

86  23  7   45  19  10 
7   10  19  23  45  86