合併排序法（mergesort）是一個典型利用
分治法（divide and conquer，D&C）解決問題的例子。其原理為不斷地將資料分成兩等分，直到每份的資料量小到一個程度後，各自排序後再一一合併起來。
假設現在有 n 筆資料需要進行排序。
則我們首先會將這 n 筆資料分成兩等分（大小皆為 n/2）；接著，再將這兩堆大小為 n/2 的資料各自分為兩等分（大小皆為 n/4）；同樣的，我們再將這四堆大小為 n/4 的資料各自分為兩等分（大小皆為 n/8）。
如此進行下去，直到每堆的資料量足夠小（例如：每堆只剩 1 筆資料）之後，我們就分別將每堆資料進行排序，再將這些資料堆兩兩一對進行合併，直到排序完成為止。
其虛擬碼大致如下：
Function mergeSort(Type data[1..n])
If n <= 1 then return
Index x, y, i, j
x = n / 2
y = n - x
Type left[1..x], right[1..y]
For i from 1 to x do
left[i] = data[i]
For i from 1 to y do
right[i] = data[x + i]
mergeSort(left)
mergeSort(right)
merge(data, left, right)
End
Function merge(Type data[1..n], Type left[1..x], Type right[1..y])
Index i, j, k
i = j = k = 1
While i <= x and j <= y do
If left[i] < right[j] then
data[k] = left[i]
i = i + 1
Else
data[k] = right[j]
j = j + 1
k = k + 1
While i <= x do
data[k] = left[i]
i = i + 1
k = k + 1
While j <= y do
data[k] = right[j]
j = j + 1
k = k + 1
End
讓我們舉個實際的例子說明：現在我們有八筆資料需要排序（由小而大）：
(84、13、73、26、32、19、91、38)
且只要每堆的資料量大於 1 時，就需要再將資料進行分割。
首先，我們先將資料分成兩等分：
(84、13、73、26) (32、19、91、38)
此時每堆的資料量為 4 (8 / 2) > 1。因此，我們還需要將每堆資料再各自分成兩等分：
(84、13) (73、26) (32、19) (91、38)
此時每堆的資料量為 2 (4 / 2) > 1。再一次，我們將每堆資料各自分成兩等分：
(13) (84) (26) (73) (19) (32) (38) (91)
此時每堆的資料量為 1 (2 / 2) = 1 ，符合停止切割的條件。所以接下來，我們要將資料兩兩合併。在合併的同時，同時確保資料排序：
(13、84) (26、73) (19、32) (38、91)
同樣的，我們將資料兩兩合併：
(13、26、73、84) (19、32、38、91)
同樣的，我們將資料兩兩合併：
(13、19、26、32、38、73、84、91)
最後，我們從時間效率上來討論合併排序法。設 merge sort 的時間複雜度函數為 T(n)。
我們可以知道，在每一次呼叫 mergeSort() 函式時，我們都需要分別將前半段與後半段的資料複製給 left 跟 right，所以複製資料的時間花費為 c1n。
然後，我們需要遞迴呼叫兩次資料大小為 n/2 的 mergeSort()，時間花費為 2T(n / 2)。最後再加上呼叫 merge() 函式所需的時間花費 c2n。所以我們可以得到：T(n) = 2T(n / 2) + cn (n > 1)，且 T(1) = 1。
若是將式子展開：T(n) = 2T(n / 2) + cn = 4T(n / 4) + 2c(n / 2) + cn = 8T(n / 8) + 4c(n / 4) + 2c(n / 2) + cn = ... = cn + cn + cn + ... + cn = cn(lg n + 1) ∈ O(n lg n)（註1）。
由此可見，合併排序的的時間效率是相當不錯的。
另外，因為有網友詢問非遞迴的合併排序法，因此試著寫了以下這個虛擬碼：
Function mergeSort(Type data[1..n])
If n <= 1 then return
Index i, j, k
For i from 2 to (n / 2) do
For j from 0 to (n - 1) step (2 * i) do
Index x, y
x = min(i, n - j)
y = min(i, max(0, n - i - j))
Type left[1..x], right[1..y]
For k from 1 to x do
left[k] = data[j + k]
For k from 1 to y do
right[k] = data[i + j + k]
Index p, q, r
p = q = 1
r = j
While p <= x and q <= y do
If left[p] < right[q] then
data[r] = left[p]
p = p + 1
Else
data[r] = right[q]
q = q + 1
r = r + 1
While p <= x do
data[r] = left[p]
p = p + 1
r = r + 1
While q <= y do
data[r] = right[q]
q = q + 1
r = r + 1
End
寫起來感覺不太直觀，如果有錯誤歡迎糾正我：）
註1. 其實可以直接利用支配定理（Master theorem）來求出複雜度 T(n)。
