歸并排序

算法原理：

現(xiàn)在還是沿用牌堆的比喻：

一共兩個(gè)操作：

1.分解：

現(xiàn)在我們將牌分為兩堆，對(duì)其中的每一堆都進(jìn)行 '分為兩堆' 這個(gè)操作，直到單個(gè)堆的元素只有一個(gè)

此時(shí)每個(gè)牌堆都是有序的

2.合并

我們對(duì)每?jī)蓚€(gè)臨近的牌堆（記為A、B）進(jìn)行：

當(dāng)前每個(gè)牌堆僅一張牌，我們比較A和B的大小，將其中較小的一張牌放在另一張的上面

以此類(lèi)推，對(duì)34、56、78...號(hào)牌堆進(jìn)行這個(gè)操作

這樣，我們獲得了若干個(gè)單個(gè)都有序的牌堆

接下來(lái)，我們繼續(xù)取臨近的兩個(gè)牌堆（記為A、B），進(jìn)行：

取出兩堆頂上的一張，比較大小，將其中較小的放入手中，重復(fù)這個(gè)操作（如果此時(shí)手中有牌，那么放于上一張的下面），直到至少一堆已空

那么這時(shí)，一共會(huì)有3種情況：
1.兩堆均空
2.A空
3.B空

對(duì)于1，我們繼續(xù)合并34、56、78...號(hào)牌堆，重復(fù)這個(gè)操作
對(duì)于2、3，顯然，此時(shí)剩余的所有元素一定比單獨(dú)的這一堆中最大的都大，讀者可以自己嘗試證明一下（提示：反證法）

那么我們可以將剩余的所有元素都直接按序排在單獨(dú)這一堆后

（嚴(yán)格證明見(jiàn)下文）

我們繼續(xù)重復(fù)合并操作，直到只剩一堆，那么此時(shí)的牌堆就是有序的，排序完成

具體算法實(shí)現(xiàn)

我們規(guī)定，a為待排序數(shù)組，共有n個(gè)元素(0 to n-1)

l為目前區(qū)間的左端點(diǎn)，r為右端點(diǎn)，mid為中間點(diǎn)

其中mid = l+(r-l)/2 (至于為什么這么做，而不是簡(jiǎn)單的(l+r)/2,請(qǐng)看下文)

開(kāi)始時(shí)，\(l = 0，r = n-1，mid = l+(r-l)/2\)
我們執(zhí)行兩個(gè)操作：

1.分解：令a分為[l,mid]、[mid+1,r]兩段，對(duì)子段繼續(xù)按此分解，直到l=r（即單一元素）

2.合并：

我們每次合并[l,mid]、[mid+1,r]兩段，保證每段內(nèi)部都是有序的
也就是說(shuō)，我們需要一個(gè)合并函數(shù)，類(lèi)似：merge(a,l,r,mid)

將[l,mid]記為L(zhǎng)，[mid+1,r]記為R，再定義一個(gè)輔助數(shù)組tmp，用來(lái)保存合并完的數(shù)組，之后拷貝到數(shù)組a

令k為當(dāng)前tmp的下標(biāo)，開(kāi)始時(shí)k=0

令i,j為當(dāng)前L、R的下標(biāo)，開(kāi)始時(shí)為0

然后：如果L[i]>=R[j]，那么tmp[k] = L[i],i--;

否則tmp[k] = R[j],j--；

重復(fù)直到至少其中一堆的top < 0（即堆中沒(méi)有任何數(shù)）；

隨后，我們將剩余的所有元素拷貝至tmp的末尾

等到合并完的區(qū)間就等于a時(shí)，算法結(jié)束， a數(shù)組有序；

循環(huán)不變式證明

P.S. 這里的證明方式更通俗，《算法導(dǎo)論》給出了另外一種證明

由于分解這一步僅僅相當(dāng)于分解問(wèn)題為多個(gè)子問(wèn)題，因此，我們不對(duì)這個(gè)階段證明循環(huán)不變式

那么，我們列出合并階段的循環(huán)不變式：

記?。涸谶^(guò)程中，我們力圖維護(hù)的，就是其循環(huán)不變式

那么，我們其實(shí)一直在維護(hù)的是tmp數(shù)組的有序性

所以，循環(huán)不變式為：

tmp[0..k]始終保存L[0..i]、R[0..j]中前k小的數(shù)

前提條件：子序列LR均有序

我們開(kāi)始證明：

1.初始化： 此時(shí)tmp中什么也沒(méi)有，因此符合循環(huán)不變式

2.保持：在算法過(guò)程中，我們有兩個(gè)階段：

• 一、在兩個(gè)子序列均非空時(shí)，我們每次取L[i]、R[j]中較小的那一個(gè)
• 二、在至少一個(gè)為空時(shí)，我們將剩余的所有元素直接移動(dòng)到tmp末尾
  
  
  
  我們挨個(gè)證明，
• 一、若取了\(L[i]、R[j]\)中較小的那一個(gè)導(dǎo)致tmp無(wú)序，那么說(shuō)明有一個(gè)數(shù)\(M>min(L[i]、R[j])\)且在tmp中，而M一定來(lái)自L、R其中一個(gè)數(shù)組；
  
  
  若M來(lái)自于\(min(L[i]、R[j])\)所在的數(shù)組，那么說(shuō)明此數(shù)組無(wú)序，于前提不符，所以不存在這樣的M，即tmp有序；
  
  
  若M來(lái)自于\(max(L[i]、R[j])\)所在的數(shù)組，那么說(shuō)明，在選擇M的那一輪循環(huán)中，M為較小的，因此另一堆剩余的所有元素一定都大于M，M這一堆剩余的所有元素也一定都大于M
  
  所以之后不會(huì)存在一個(gè)比M小的數(shù)\(min(L[i]、R[j])\)了，與前提不符，所以不存在這樣的M；
  
  
• 二、若這個(gè)操作導(dǎo)致tmp無(wú)序，那么在剩余這一堆中一定存在一個(gè)數(shù)Q，使得\(Q<tmp[k]\)，那么，tmp[k]只可能來(lái)自L、R
  
  如果和Q同堆，那么由于\(Q<tmp[k]\)，說(shuō)明此堆無(wú)序，所以不存在Q
  若不同堆，那么說(shuō)明這一堆剩余所有元素均大于tmp[k]，則剩余的堆應(yīng)該是這一堆，與假設(shè)不符；

\(Q.E.D\)

形式化的循環(huán)不變式證明：

形式化定義：
設(shè) \(L[1..m]\) 和 \(R[1..p]\) 為有序數(shù)組，合并時(shí)不變式：
\(temp[1..k]\) 包含 \(L[1..i]\) 和 \(R[1..j]\) 中前 \(k\) 小元素且有序

數(shù)學(xué)歸納證明：

初始化：\(k=0, i=1, j=1\)，空數(shù)組滿足條件
保持：
若 \(L[i] \leq R[j]\)，則 \(L[i]\) 是剩余元素最小者
由歸納假設(shè) \(temp[1..k]\) 有序，追加 \(L[i]\) 仍有序
終止：\(i>m\) 或 \(j>p\) 時(shí)，剩余元素直接追加仍有序

為什么是mid = l+(r-l)/2

我們先嘗試展開(kāi)：
\(mid = l+(r-l)/2 = l+0.5r-0.5l = 0.5r+0.5l = 1/2(r+l)\);

與直接\(mid = (l+r)/2\)本質(zhì)上是一致的

那么為什么還要變形呢

想這樣一個(gè)問(wèn)題：倘若r、l均取int類(lèi)型的最大值的一半+1，\(mid = (l+r)/2\)會(huì)發(fā)生什么呢

顯然，\(l+r\)超過(guò)了int類(lèi)型的最大值，會(huì)導(dǎo)致溢出

綜上，我們選擇\(mid = l+(r-l)/2\)；

關(guān)于位運(yùn)算的一些奇技淫巧

我們注意到：在\(mid = l+(r-l)/2\)中需要計(jì)算一個(gè)\(/2\)的操作
那么，有請(qǐng)位運(yùn)算——快速乘除法
原理 ：在進(jìn)行乘除運(yùn)算時(shí)，如果乘數(shù)或除數(shù)是 2 的冪次方，可以利用位移運(yùn)算來(lái)替代乘除法操作
左移一位相當(dāng)于乘以 2，右移一位相當(dāng)于除以 2
例如，num << n 等價(jià)于 num * 2^n，num >> n 等價(jià)于 num / 2^n
所以，我們可以改為：mid = (l+(r-l))>>1 （位運(yùn)算的優(yōu)先級(jí)更低，需要單獨(dú)加括號(hào)）
Upt 2025.8.6
GhostSilver