《算法基礎：打開算法之門》一3.4 歸并排序

本節書摘來自華章出版社《算法基礎：打開算法之門》一書中的第3章，第3.4節，作者 ［美］托馬斯 h 科爾曼（thomas h cormen），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

我們的下一個排序算法是歸并排序，對于所有情況，它有一個僅僅Θ（nlgn）的運作時間。當将它的運作時間和選擇排序與插入排序的最壞運作時間Θ（n2）進行比較時，我們僅僅是将n這個因子替換成了lgn這個因子。正如我們在第1章中所指出的那樣，這是一個非常劃算的交易。

歸并排序與我們已經看到的兩種排序算法相比有一些不足。首先，隐含在漸近符号前面的常量因子比另外兩個算法的漸近符号前面的常量因子的值大。當然，一旦數組規模n變得非常大，那個常量因子也變得沒有那麼重要了。第二，歸并排序不是原址的（in place）:它必須将整個輸入數組進行完全的拷貝。而選擇排序和插入排在任何時間僅僅拷貝一個數組項而不是對所有數組項都進行拷貝。如果空間非常寶貴，那麼你可能并不會使用歸并排序。

我們在歸并排序中使用一個被稱為分治法的通用模式。在分治法中，我們将原問題分解為類似于原問題的子問題，并遞歸地求解這些子問題，然後再合并這些子問題的解來得出原問題的解。回憶一下，在第2章中，為了執行遞歸操作，每次遞歸調用必須在同樣問題的一個更小的執行個體上進行，最終會抵達一個基礎情況。下面是分治算法的一般概述。1分解：把一個問題分解為多個子問題，這些子問題是更小執行個體上的原問題。2解決：遞歸地求解子問題。當子問題足夠小時，按照基礎情況來求解。403合并：把子問題的解合并成原問題的解。當使用歸并排序對書架上的書進行排序時，每個子問題包括對書架上連續位置的書籍的排序。初始時，我們想要對n本書進行排序，即從位置1到位置n，但在一般子問題中，我們想要對從位置p到位置r的書進行排序。下面講解我們如何應用分治法。1分解：通過找到位于p和r中間位置的數字q對問題進行分解。正如在二分查找中查找中間點一樣，我們進行同樣的操作，将p和r加起來，将該和除以2，并向下取整。2解決：對分解步驟得出的兩個子問題的書進行遞歸排序，對從位置p到位置q的書籍進行遞歸排序，且對從位置q+1到位置r的書籍進行遞歸排序。3合并：将從位置p到q的排序好的書籍和從位置q+1到r的排序好的書籍進行合并，使得從位置p到位置r的書籍排好序。我們将馬上介紹如何合并書籍。當少于兩本書籍需要排序（也就是p≥r）時，基礎情況會發生，因為不包含書的書集或者隻擁有一本書的書集已經是排好序的。為了将這個觀點轉換成對數組進行排序，從位置p到位置r的書對應于子數組a［pr］。下面是歸并排序程式，它會調用一個程式merge(a,p,q,r)，該程式會将排好序的子數組a［pq］和a［q+1r］合并為單一的排好序的子數組a［pr］。

盡管還不清楚merge程式是如何運作的，我們先看看mergesort程式運作的一個例子。我們以下面這個數組為例：

初始調用是mergesort(a,1,10)。第2a步計算出q為5，是以第2b步和第2c步的遞歸調用是mergesort(a,1,5)和mergesort(a,6,10)。

經過兩次遞歸調用後，這兩個子數組排序如下：

最終，在第2d步中調用merge(a,1,5,10)将兩個排好序的子數組歸并為一個單一的有序子數組，以下是這種情況下的整個數組：

如果展開遞歸，我們會得到以下圖像。分叉箭頭表明分解步驟，彙聚箭頭表明歸并步驟。出現在每個子數組上方的變量p、q和r指每次遞歸調用過程中對應的索引。斜體數字給出了經過初始調用mergesort(a,1,10)後程式調用發生的次序。例如，merge(a,1,3,5)是經過初始調用後的第13步的調用，mergesort(a,6,7)是第16步的調用。真正的工作發生在merge程式中。是以，merge程式不僅必須正确地運作，而且它必須運作很快。如果要歸并一個總數為n的數組，由于每個元素必須調整至适當位置上，是以我們能設想的最好情況是Θ（n）時間，并且确實能夠實作線性時間的歸并。

繼續參考書架那個例子，讓我們隻觀察位于位置9～位置14的那部分書籍。假設已經排列好位置9～11的那部分書籍和位置12～14的那部分書籍。

我們将位置9～11的書籍組成一個堆，把按照字母排序作者名字排在最前面的書籍放在頂側，并且對位置12～14的書籍按照相同的規則進行操作，制作成另外一個堆：

因為這兩個堆都已經排好序了，是以那本應該放置在位置9的書籍一定是這兩個堆頂側書籍中的一個：gustave flaubert或者charles dickens寫的書籍。根據作者名字的字典序，dickens寫的書籍應該排在flaubert寫的書籍的前面，是以我們将dickens寫的書籍移動到位置9處：

把dickens所寫的書籍放置在位置9後，放置在位置10處的書籍或者是置于第一個堆頂側的書籍（即由flaubert所寫的書籍），或者是目前第二個堆的頂側的書籍（即由jack london所寫的書籍）。同理，我們将由flaubert所寫的書籍移動至位置10處：

下一步，我們比較位于目前兩個堆頂側的書籍，即由jonathan swift和london所寫的書籍，并且将london所寫的書籍移動至位置11處。這導緻sir walter scott所寫的書籍位于右邊堆的頂側，将它與swift所寫的書籍進行比較，我們将scott所寫的書籍移動到位置12處。此時，右邊那個堆便為空：

剩下的操作是将位于左側堆的書籍按序放到餘下的位置處。現在位于位置9～14的所有書籍是有序的：

這個歸并程式的效率如何呢？我們對每本書籍均進行了兩次移動：一次是從書架上取下來并且将它放入一個堆上，另一次是将它從堆的頂側移回到書架上。而且，每當決定将哪本書移回書架上時，我們僅僅需要比較兩本書：那些在堆頂側的書籍。是以，為了合并n本書籍，我們移動了2n次并且對成對的書籍至多比較n次。為什麼要将書籍從書架上移動下來呢？要是将書籍保留在書架上，僅僅記錄下哪本書已經放置在了書架上的正确位置上，45哪本書并沒有放置在正确的位置上呢？那可能會導緻更多的工作。例如，假定右半側的每本書都應該出現在左半側的每本書之前。在将右半側的第一本書籍移動到左半側的第一個位置之前時，我們必須将左半側的每本書籍依次向右移動一個位置以騰出空間。并且之後對于出現在右半側的下一個書籍，在将它移動到左半側書籍的第二個位置之前，我們也必須進行同樣的操作。針對右半側的其餘書籍也必須進行同樣的操作。是以，每次想要将右半側的一本書籍放置在它的正确位置上時，我們将必須移動一半的書籍——所有左半側的書籍。上述論據證明了我們為什麼不進行原址歸并。實際上，可以線上性時間内實作原址歸并，但是實作該程式相當複雜。下面回到如何将排好序的子數組a［pq］和a［q+1r］歸并為a［pr］的問題上。我們首先将數組a中要歸并的元素拷貝到臨時數組中，随後将臨時數組中的元素再歸并到數組a中。令n1=q-p+1是數組a［pq］中的元素數目，且n2=r-q是數組a［q+1r］中的元素數目。我們建立包含n1個元素的臨時數組b和包含n2個元素的數組c，并且按序将數組a［pq］中的元素拷貝至b中，同樣地，我們按序将數組a［q+1r］中的元素拷貝至c中。現在重新将這些元素歸并到a［pr］中而不用擔心覆寫它們僅有的備份。我們像歸并書籍一樣歸并數組元素。将數組b和數組c中的元素重新拷貝至子數組a［pr］中，記錄目前數組b和c中還沒有被拷貝到a的值的最小元素的索引，然後将其中較小的元素拷貝到數組a。我們能夠在常量時間内斷定兩個元素中哪個元素較小，并将它拷貝至a［pr］中的正确位置上，并更新元素的索引。最終，其中一個數組的所有元素均拷貝至a［pr］中。這也意味着隻剩下一個書堆。為了避免每次檢查是否其中一個數組已經為空，我們使用以下技巧：在數組b和c的最右側放置一個大于任意元素的值。想起我們在第2章的sentinellinearsearch中所使用的标記技巧了嗎？是的，這一思路是類似的。這裡，我們使用∞(無窮)作為标記的排序關鍵字，46以便當一個帶有∞的關鍵字是該數組中剩餘的最小元素時，它確定了“無需”檢查哪個數組有更小的剩餘元素。實際上，我們可以令∞取任意一個比所有排序關鍵字大的值。例如，如果排序關鍵字是作者名字，那麼∞可以取zzzz——當然，假定真實的作者名字中不會取zzzz這個值。一旦來自數組b和c的所有元素全部拷貝完成，這時兩個數組均以它們的标記作為最小剩餘元素。但是此時沒有必要比較标記大小，因為到那時我們已将所有的“真實”元素（非哨兵元素）拷貝至a［pr］。由于我們提前知道會将所有元素拷貝～a［p］到a［r］中，當将一個元素拷貝至a［r］時，我們就結束操作。是以，我們僅僅需要在a的索引上運作一個從p到r的循環即可。以下是歸并程式。雖然看起來很長，但是它剛好采用了上面介紹的方法。

經過步驟1～4，實作了對數組b和c的指派操作，将a［p…q］拷貝至b且将a［q+1r］拷貝至c，并且将标記插入到這些數組中，47在第6步的主循環的每次疊代中，将最小的剩餘元素拷貝至a［pr］的下一位置上，一旦它将b和c中的所有元素拷貝完畢就終止。在這個循環疊代中，i指向b中最小的剩餘元素，j指向c中最小的剩餘元素，k指向a中的元素要拷貝的位置。如果要将n個元素合并在一起（以便n=n1+n2），将元素拷貝至數組b和c中會花費Θ（n）時間，将每個元素又拷貝回a［pr］需要花費常量時間，是以全部的歸并操作僅僅需要Θ（n）時間。我們之前宣稱整個歸并操作算法需花費Θ（nlgn）時間。我們做最簡單的假定，即數組大小n是2的幂，以便每次分解數組時，子數組大小是相等的。（一般而言，n可能不是2的幂且在一個給定遞歸調用中，子數組大小可能是不相等的。如果考慮這些，則需要一個嚴格的分析證明，此時我們不考慮這些細節。）我們對歸并排序進行如下分析。假定排序一個包含n個元素的子數組需要花費t(n)時間，它是一個随着n增加的函數（假定排序更多的元素會花費更長的時間）。時間t(n)來自于分治模式的三個部分所耗費時間的累加和：1分解花費常量時間，因為它隻計算了索引q。2解決包括關于兩個子數組的遞歸調用，每個子數組有n/2個元素。現在我們定義了排序一個子數組的時間，每個子數組的遞歸調用需花費t(n/2)時間。3通過合并排序好的子數組來合并這兩個遞歸調用的結果需要花費Θ（n）的時間。因為與合并操作所需的Θ（n）時間相比，分解所需花費的常量時間是一個低階項，是以可以将分解時間并入合并時間，并稱分解和合并一共花費Θ（n）的時間。解決步驟花費t(n/2)+t(n/2)時間，即2 t(n/2)時間。現在我們對t(n)寫一個等式：

其中f(n)代表分解和合并操作所花費的時間，如我們剛剛得出的，分解和合并操作共花費的時間是Θ（n）。48在算法學習過程中的一個常見做法是對等式進行近似且将我們所不關心的内容歸結為一個函數，是以将該等式重寫為

等等！這裡似乎存在一些缺陷。我們已經定義了函數t，它用來描述類似的歸并排序的運作時間！我們稱這樣一個等式為一個遞歸式，或者稱為一個遞歸。問題是我們想将t(n)表達為非遞歸形式，也就是說，表示成并不關于它本身的一個函數。将一個表示成遞歸形式的函數轉化為非遞歸形式可能是一個瓶頸，但是對于相當一大類遞歸式我們能運用一個被稱為“主方法”的标準化方法。主方法适用于許多形為t（n)=at（n/b）+f(n)的遞歸（但并非所有），其中a和b是正整數。幸運的是，它适合于我們的歸并排序遞歸，并且給出了結果，t(n)為Θ（nlgn）。該Θ（nlgn）的運作時間适合于歸并排序的所有情況——最好情況、最壞情況和介于這兩個情況之間的所有情況。每個元素均被拷貝了Θ（lgn）次。你能從merge方法中看到，當它以p=1和r=n被調用時，它會對所有的n個元素進行拷貝，是以歸并排序一定不是原址的。