歸并排序（Merge Sort）是建立在歸并操作上的一種有效的穩(wěn)定的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。

歸并排序?qū)蓚€有序的子序列合并得到一個完全有序的序列，即先使每個子序列有序，再使子序列段間有序。若將兩個有序的列表合并成一個有序的列表，我們稱之為二路歸并。

歸并排序的速度僅次于快速排序，時間復(fù)雜度為O(nlogn)。其拆分過程中使用了二分思想，是一個遞歸的過程，為了減少在遞歸過程中不斷開辟空間的問題，我們可以在歸并排序之前，先開辟出一個臨時空間，在遞歸過程中統(tǒng)一使用此空間進行歸并即可。

例如：

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();
    }
}

運行結(jié)果如下：

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