背景介紹： 是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為O(n log n)。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，且各層分治遞歸可以同時(shí)進(jìn)行。 ----- 來自 wikipedia

算法規(guī)則： 像快速排序一樣，由于歸并排序也是分治算法，因此可使用分治思想：
1.申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
2.設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3.比較兩個(gè)指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置
4.重復(fù)步驟3直到某一指針到達(dá)序列尾
5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾

代碼實(shí)現(xiàn)（Java版本）

    public void mergeSort(int[] ints, int[] merge, int start, int end) 
    {
        if (start >= end) return;

        int mid = (end + start) >> 1;

        mergeSort(ints, merge, start, mid);
        mergeSort(ints, merge, mid + 1, end);

        merge(ints, merge, start, end, mid);

    }

    private void merge(int[] a, int[] merge, int start, int end,int mid) 
    {
        int i = start;
        int j = mid+1;
        int pos = start;
        while( i <= mid || j <= end ){
            if( i > mid ){
                while( j <= end ) merge[pos++] = a[j++];
                break;
            }

            if( j > end ){
                while( i <= mid ) merge[pos++] = a[i++];
                break;
            }

            merge[pos++] = a[i] >= a[j] ? a[j++] : a[i++];
        }

        for (pos = start; pos <= end; pos++)
            a[pos] = merge[pos];

    }