事實上，讓C語言程式設計具有魅力的是演算法，拿到問題，能夠設計出解決方案並且完成程式碼的是程式設計師，只會按照步驟編碼的是碼農。

什麼樣的演算法才是好的演算法呢？

假設計算機是無限快的，並且儲存器是免費的無限大的，那最好的演算法就是最容易實現的演算法。

然而，計算機也許是快的，但它們不是無限快。儲存器也許是廉價的，但不是免費的。所以計算時間是一種有限資源，儲存器的空間也一樣。優秀的程式設計師應該盡力設計出開銷更小的演算法。

什麼是歸併排序呢？

歸併排序的定義，希望瞭解“一本正經”的官方書面定義可以自行百科。這裡就不寫了，因為“冷冰冰的”書面定義對不瞭解它的人來說太難懂。

我打算用一些容易理解的例子來解釋它。

假設有一個C語言陣列需要排序，那陣列長度為多長最簡單呢？顯然是長度為 1 時，排序最簡單，什麼都不需要做，就能夠排好序。

歸併排序的基本思路就是這樣：把長陣列一直拆分下去，直到最後不能拆分為止，這時長陣列被拆分為若干個長度為 1 的陣列，長度為 1 的陣列顯然是排好序的了。

例如下圖是一個長度為 5 的陣列，為了排序，先把它拆分到不能繼續拆為止。

接著，只要把這些排好序的子陣列按照從小到大的順序合併，就可以得到最終排好序的陣列了。

好了，現在知道歸併排序的演算法了，那怎樣使用 C語言程式設計完成這個演算法呢？

使用C語言程式設計實現歸併排序演算法

歸併排序演算法總體可以分為兩步：拆分陣列，合併陣列。先來看看怎樣使用C語言實現陣列的拆分。

使用C語言拆分陣列

對陣列拆分有多種方法，這裡選擇平分法。

如果使用 start 表示陣列頭，end 表示陣列尾，每次平均拆分，都會將陣列分為 start 到 mid，和 mid+1 到 end 兩部分，其中 mid 表示中間點，所以 mid = (start+end)/2。就這樣一直拆分下去，直到不能繼續拆分為止。

不能拆分時，start 應該不再小於 end。

拆分陣列的數學描述完畢了，容易看出，遞迴（如果題主對C語言的遞迴不理解，可以檢視我之前的問答或者文章。）非常適合解決這樣的問題。我們現在用C語言來實現這樣的拆分，先確定遞迴的基礎條件：

拆分過程會在 start 不再小於 end 時停下。其他情況時，拆分會繼續下去，相關C語言程式碼如下，請看：

divide(start, mid); 負責拆分前半段，divide(mid+1, end); 負責拆分後半段。這樣的 divide 函式可以把陣列拆分到不可拆分為止。

使用C語言合併陣列

使用 divide 函式把陣列拆分完畢後，就可以按照從小到大的順序把各個元素合併到原來的陣列了。

由於兩個子序列都已經排好序了，所以 merge() 函式的C語言程式碼很簡單，每次迴圈取兩個子序列中最小的元素進行比較，將較小的元素取出放到最終的排序序列中，如果其中一個子序列的元素已取完，就把另一個子序列剩下的元素都放到最終的排序序列中。

使用C語言實現陣列的歸併排序

陣列的拆分和合並函式都寫好了，可以把它倆結合起來，實現陣列的排序了。

測試C語言實現的歸併排序

這裡使用 8 個元素的陣列做測試：

編譯並執行這段C語言程式碼，發現數組被成功排序了。

到這裡，相信題主應該明白如何使用C語言實現陣列的歸併排序了。它和插入排序演算法都屬於排序演算法，但是二者的效率差異性卻很大。

學習演算法是有基礎要求的，尤其是一些複雜的演算法，比如：離散數學，數理邏輯，資料結構等，所以學習演算法肯定會覺得難。演算法的好壞評估標準通俗的講就是效率高低，不僅包括時間效率，還包括空間效率。演算法學習建議先學習一些簡單的，再逐步深入。