1. 歸并排序（遞歸版）

歸并排序（MERGE-SORT）是利用歸并的思想實(shí)現(xiàn)的排序方法，該算法采用經(jīng)典的分治策略，即分為兩步：分與治。

1. 分：先遞歸分解數(shù)組成子數(shù)組
2. 治：將分階段得到的子數(shù)組按順序合并

我們來(lái)具體看看例子，假設(shè)我們現(xiàn)在給定一個(gè)數(shù)組：[6，3，2，7，1，3，5，4]，我們需要使用歸并算法對(duì)其排序，其大致過(guò)程如下圖所示：

分階段可以理解為就是遞歸拆分子序列的過(guò)程，遞歸的深度為log2n。而治的階段則是將兩個(gè)子序列進(jìn)行排序的過(guò)程，我們通過(guò)圖解看看治階段最后一步中是如何將[2，3，6，7]和[1，3，4，5]這兩個(gè)數(shù)組合并的。

圖中左邊是復(fù)制的臨時(shí)數(shù)組，而右邊是原數(shù)組，我們將左右指針對(duì)應(yīng)的值進(jìn)行大小比較，將較小的那個(gè)數(shù)放入原數(shù)組中，然后將相應(yīng)的指針右移。比如第一步中，我們比較左邊指針L指向的4和右指針R指向的1，R指向的1小，則把1放入原數(shù)組中的第一個(gè)位置中，然后R指針向右移動(dòng)。后面再繼續(xù)，直到左邊臨時(shí)數(shù)組的元素都按序覆蓋了右邊的原數(shù)組。最后我們通過(guò)上圖再結(jié)合源碼來(lái)看看吧：

class Solution {
    public int[] sortArray(int[] nums) {
        sort(0, nums.length - 1, nums);
        return nums;
    }

    // 分：遞歸二分
    private void sort(int l, int r, int[] nums) {
        if (l >= r) return;

        int mid = (l + r) / 2;
        sort(l, mid, nums);
        sort(mid + 1, r, nums);
        merge(l, mid, r, nums);
    }


    // 治：將nums[l...mid]和nums[mid+1...r]兩部分進(jìn)行歸并
    private void merge(int l, int mid, int r, int[] nums) {
        int[] aux = Arrays.copyOfRange(nums, l, r + 1);

        int lp =l, rp = mid + 1;

        for (int i = lp; i <= r; i ++) {
            if (lp > mid) {                // 如果左半部分元素已經(jīng)全部處理完畢
                nums[i] = aux[rp - l];
                rp ++;
            }  else if (rp > r) {          // 如果右半部分元素已經(jīng)全部處理完畢
                nums[i] = aux[lp - l];
                lp ++;
            } else if (aux[lp-l] > aux[rp - l]) {     // 左半部分所指元素 > 右半部分所指元素
                nums[i] = aux[rp - l];
                rp ++;
            } else {                                  // 左半部分所指元素 <= 右半部分所指元素
                nums[i] = aux[lp - l];
                lp ++;
            }
        }
    }
}

我們可以看到，分階段的時(shí)間復(fù)雜度是logN，而合并階段的時(shí)間復(fù)雜度是N，所以歸并算法的時(shí)間復(fù)雜度是O(N*logN)，因?yàn)槊看魏喜⒍夹枰獙?duì)應(yīng)范圍內(nèi)的數(shù)組，所以其空間復(fù)雜度是O(N);

2. 歸并排序（迭代版）

上面的歸并排序是通過(guò)遞歸二分的方法進(jìn)行數(shù)組切分的，其實(shí)我們也可以通過(guò)迭代的方法來(lái)完成這步，看下圖：

其因?yàn)閿?shù)組，所以我們直接通過(guò)迭代從1開(kāi)始合并，其中sz就是合并的長(zhǎng)度，這種方法也可以稱為自底向上的歸并，其具體的代碼如下

class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        // sz= 1,2,4,8 ... 排序
        for (int sz = 1; sz < n; sz *= 2) {
            // 對(duì) arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 進(jìn)行歸并
            for (int i = 0; i < n - sz; i += 2*sz ) {
                merge(i, i + sz - 1, Math.min(i+sz+sz-1, n-1), nums);
            }
        }
        return nums;
    }

   // 和遞歸版一樣
    private void merge(int l, int mid, int r, int[] nums) {
        int[] aux = Arrays.copyOfRange(nums, l, r + 1);

        int lp =l, rp = mid + 1;

        for (int i = lp; i <= r; i ++) {
            if (lp > mid) {
                nums[i] = aux[rp - l];
                rp ++;
            }  else if (rp > r) {
                nums[i] = aux[lp - l];
                lp ++;
            } else if (aux[lp-l] > aux[rp - l]) {
                nums[i] = aux[rp - l];
                rp ++;
            } else {
                nums[i] = aux[lp - l];
                lp ++;
            }
        }
    }
}

3. 總結(jié)

好了，歸并算法就介紹完了，再來(lái)總結(jié)一下：

歸并排序是一種十分高效的排序算法，其時(shí)間復(fù)雜度為O(N*logN)。歸并排序的最好，最壞的平均時(shí)間復(fù)雜度均為O(nlogn)，排序后相等的元素的順序不會(huì)改變，所以也是一種穩(wěn)定的排序算法。歸并排序被應(yīng)用在許多地方，其java中Arrays.sort()采用了一種名為TimSort的排序算法，其就是歸并排序的優(yōu)化版本。