常用内部排序算法之一：歸并排序

前言

歸并排序是所有常用内部排序算法中穩定性最好的，無論是平均時間複雜度、最壞時間複雜度還是最好時間複雜度，其時間複雜度都是o(nlogn)。由于這個特性，在需要考慮排序穩定性的情況下，歸并排序是所有優化算法（直接插入排序、冒泡排序和簡單選擇排序）使用最多的。其實歸并排序算法的思想很簡單：假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每一個子序列的長度都是1，然後把這些子序列兩兩歸并，得到⌈n/2⌉（⌈x⌉表示不小于x的最小整數）個長度為2或者1的有序子序列；再兩兩歸并，……，如此重複，直至得到一個長度為n的有序序列為止。這種方法也被稱為2路歸并排序。

首先看代碼的實作過程：

下面以序列{50,10,90,30,70,40,80,60,20}為例，說明歸并排序的具體過程：

初始時刻，msort方法中的數組b和數組a都是{50,10,90,30,70,40,80,60,20}

i = 0，j = 9,顯然兩者不相等，将數組b分為b[i…m]和b[m+1…j]，此時m = 5，也就是數組b 正中間下标

然後遞歸調用msort函數，繼續将b[0…5]和b[6…9]拆成兩組，直到每組隻有一個元素

兩次遞歸調用msort函數之後，b[0…5]和b[6…9]已經排好序了，最後将這兩組排好序的數組繼續歸并成最終排好序的數組，這個過程調用的是merge函數，該函數的主要目的就是将最好的兩組進行歸并排序

将排好序的數組傳回給原數組a，排序結束

歸并排序小結

由于歸并排序在歸并過程中需要與原始記錄序列同樣數量的存儲空間存放歸并結果以及遞歸時深度為log2n的棧空間，是以歸并排序的空間複雜度是o(n+logn)。

歸并排序的總的時間複雜度是o(nlogn)，同時這也是最好、最壞、平均的時間複雜度。需要注意的是，歸并排序的是一種穩定的排序算法，但是歸并排序是比較占用記憶體的。