合併排序(merge sort 或 mergesort)是另一種採用分治法的排序演算法。
它的步驟是：

1. 分割：用遞迴的方式，將長度為n的數列分成兩半，直到子數列長度為1。
2. 合併：將上一步的子數列合併成為一個有序數列。

舉例來說，這是對七個元素的數列進行合併排序的圖：

圖片來源：維基百科

圖的上半是反覆將原數列分成兩半，直到分割成七個長度為一的子數列。這部分遞迴想法跟上一回快速排序很接近，就是當數列被分解到最小單位時，可以當作已經排序完成。

接下來合併的步驟，就是依序將兩個相鄰子數列的元素進行比較，並合併在一起。舉例來說，(27, 38)與(3, 43)兩個子數列的合併，就是27與3比較，接著27與43比較，接著38與43...每次比較都把較小的數字加入新陣列。最終所有的子數列合併即為排序好的數列。

執行時間

合併排序先是反覆將數列分成兩半，所以這部分執行時間是我們熟悉的O(log n)。而後面每一層的合併則都要操作所有n個元素一遍，所以兩者相乘，合併排序的操作時間為O(n log n)。而在最佳情況，合併排序的執行時間也是Ω(n log n)，即便是操作有序數列，合併排序也是進行同樣的步驟。

快速排序 vs. 合併排序

看到這裡，眼尖的人會有這樣的疑問：如果上一回的快速排序平均執行時間才O(n log n)，最壞會是O(n²)，可是合併排序最壞就是O(n log n)，那那那，當然是用合併排序啊？

事實上，快速排序達到O(n log n)的比例很高，且實務中常常比同為O(n log n)的合併排序還有效率，所以仍然是許多排序任務的首選。而合併排序對於操作某些資料結構特別有效，例如只能循序存取(sequential access，只能以特定順序取值，無法隨機存取)的資料結構。

另一個快速排序比合併排序更有優勢的地方在於空間需求較少。快速排序進行的是原地(in-place)操作，因為是透過反覆交換元素完成排序，主要在原輸入陣列上操作即可，只需要少量額外記憶體空間。而通常合併排序在每一階段的合併都需要新的空間來儲存合併的陣列，空間需求較高。

排序演算法操作比較

從一開始的選擇排序到現在的合併排序，討論了很多排序方式。以下影片是一些排序演算法的比較，用視覺化的方式表現各個演算法在輸入不同(例如隨機、排序完全顛倒、幾乎已排序好的情況)時的表現。