浙江大學-數據結構-歸併排序-9.4.3

非遞歸演算法

那之所以我們先介紹一個遞歸的演算法呢，是因為我們覺得遞歸演算法可能比較容易理解一點，當然了，數據結構學到現在，我相信你已經知道遞歸演算法在真正實現的時候，其實並不是那麼美妙的，因為它要佔用系統的堆棧，而且它有很多額外的操作都讓它比較慢，那麼歸併排序有沒有可能用不遞歸的演算法做出來呢？當然可以，而且呢，其實也沒有那麼複雜，非遞歸演算法的一個基本思路是這樣的，我假設在一開始的時候，我一共有n個有序的子序列，每一個子序列里都只含有一個元素，然後下一步我要做的就是，把相鄰的有序的子序列做一次歸併，於是呢，我就形成了若干個有序的子序列，每個子序列的長度就變成了2。

就每個子序列裡面包含兩個元素，這兩個元素之間是有序的，然後我繼續歸併兩個相鄰的子序列，又產生了一系列有序的子序列，這些子序列的長度就變成了4，

以此類推，一直到最後，我得到了一個完整的有序的序列，

整個演算法過程呢，其實是非常容易理解的，有一點麻煩就是我們看看到底要多少額外的空間，如果是照著這個圖來理解的話，這個額外的空間複雜度，好像有點恐怖，它一共迭代了多少層呢？就是每次乘以2，每次乘以2，一直到最後得到n為止，那麼它這個深度有多少呢？這一共是logN,對不對？如果在每一層，我要去開一個新的臨時數組去存中間結果的話，那麼我的額外空間複雜度就變成一個多麼可怕的景象了？但是，換一個角度講，真的有必要這麼做嗎？如果我們要用非遞歸演算法去實現歸併排序的話，你能夠做到最小的額外空間複雜度是多少呢？

是O(N)

實際上我們需要每次都開一個臨時數組嗎?當然沒有必要，聰明一點的話，實際上我們只要開一個臨時數組就夠了，原來那個A也不是不可以用的，那第一次呢，我們把這個A給它歸併到臨時數組裡面去，第二次呢，我其實就可以把臨時數組裡面的東西歸併回到A裡面去，然後再把A導到臨時數組裡頭，再把臨時數組導回到A,那最後一步呢，那要看我們的運氣了，如果運氣好的話，最後一步這個就是A,那我們就完事大吉，就退出了，如果運氣不好呢，那最後這一步可能是那個臨時數組,它不是A,但是也沒關係的，我們最多就把這個臨時數組再加一步，導回到A裡面去就可以了，所以在整個的執行過程中，它的核心步驟就是一趟歸併，那這一趟歸併的偽代碼要怎麼寫呢？我們來看一下

我們把一趟歸併的函數取個名字叫做Merge_pass,傳進來的東西呢，仍然是原始的數組加上臨時數組，這個N是整個待排序列的長度，然後多了一個length,這個length指的是當前有序子列的長度，也就是說這個length在一開始的時候，是等於1的，我們假設每一個數字自己就是一個有序的子列，然後這個length在執行的過程中，每一次是要加倍的，在我們之前已經討論過的Merge函數以後呢，這件事情就變得非常簡單，那我這一步執行的其實就是從左到右一對一對的去調用那個Merge,每一次給的是這個i是它最左邊的位置，i+length是跳過這麼長一段，下一段的初始位置，下一段的終止位置呢，就是i+2*length-1,每一次循環的時候呢，i要加上兩倍的length,就是跳過兩段，然後去找下一對，為什麼這個Merge我在這寫成了Merge1呢？它跟原始的Merge稍微有點不一樣，原始的歸併函數在歸併完了以後，那個有序的結果一定是放在A裡面的，就雖然我把結果先導到了TmpA里，最後還是要TmpA導回到A裡面去的，但是呢,Merge1裡面我們不做最後的這一步，我調用Merge1的時候，就意味著我是把A中的元素歸併到TmpA裡面去的，最後有序的內容是放在TmpA裡面，那我們來注意一下，這個循環結束的條件，這個循環不是執行到N的時候結束的，而是執行到N-2*length結束的，為什麼會這樣呢？因為我們去想一下，前面我們是一對一對做歸併的，正好歸併完成的前提條件是說你要歸併的子序列正好是偶數個，它正好是成對的，如果它是奇數個呢，那麼它最後就會多出一個來，歸併到最後的時候呢，最後兩段有序序列的長度都可能不一樣，所以那個尾巴是一件很麻煩的事情，那尾巴另外處理，我先把前面保證都是成對的那一部分先給它處理完，所以我只處理到倒數第二對，把這個處理完了以後，我再看尾巴，

在當前的這個i,如果加上了一段以後，還是小於N的，那麼就說明我最後是不止一個子列，最後是有兩個子列的，那麼我繼續去調用Merge1,把最後這兩個子列，也注意到最後一個子列的結尾無論如何都是N-1,把最後兩個子列都歸併一下，如果這個條件不成立(if (i+length < N)),意味著什麼呢？意味著在當前i這個位置加上了一個length之後，它就跳到N外面去了，也就意味著最後我只剩下一個子列了，我就直接把剩下的A直接導到TmpA裡面去，就完了。這樣就完成了我們一趟的歸併。

接下來我們再看我們那個原始的統一的介面，應該怎麼寫，我們真正拿出來見人的介面，Merge_sort傳進來的是原始的A和它的個數N,然後在這裡面呢，我們聲明了一個跟原始數組等長的一個臨時數組，TmpA,如果我們有足夠的時間的話呢，我們就繼續，否則的話呢，我們就要宣稱空間不足，那在我做完了中間這堆事情以後呢，我要記得把TmpA給free掉，那這些都是細節問題，最關鍵的是說，如果我們拿到了這個空間，我們就要開始往裡面做這個Merge_pass，在最開始的時候，我們假設的有序子列長度是等於1， 那我們先初始化子序列的長度

然後我們把這個length帶到Merge_pass裡面去，調用了一次Merge_pass以後呢，這個A就被導到了TmpA裡面。

length是當前的1，執行完了1次Merge_pass以後，那麼當前有序的子序列，它的長度就變成了2，然後我再調用1次Merge_pass的時候，傳進去的這個長度，就是2，接下來我要做的就是把前一步的結果，是放在TmpA裡面的，再導回到A裡面去，所以TmpA和A的位置要換一下，前面TmpA是初始狀態，後面A是歸併以後的狀態，執行完了這個Merge_pass以後，這個length再次double,變成了4，那在這裡頭呢，每一次循環我都做兩步的Merge_pass,這樣能夠保證當我這個while循環裡面跳出來的時候，無論如何，最終的結果都是存在A裡面的，哪怕它最後一步，比如說我執行到這一步的時候(Merge_pass(A, TmpA, N, length)),它已經完全有序了，那這個時候，length就已經等於N了，那也沒關係，我多執行一步這個Merge_pass會發生什麼事情呢，這個時候在Merge_pass裡面執行的實際上就是TmpA原封不動的導到A裡面，什麼都沒有做，然後我們就會自然的跳出，這個while循環的條件是什麼呢？就是當這個length還沒有達到N的時候，我們就一直在循環，一直到length>=N的時候，我們就可以跳出來了，Merge_sort有一個非常好的性質，它是穩定的，我們前面說了Merge_sort歸併排序有各種各樣的好處，包括它的平均複雜度，是nlogn,最壞時間複雜度也是nlogn,而且它還是穩定的，但有一點不好，就是它需要一個額外的空間，並且它需要在數組和數組之間來回導這個元素，這是它最大的缺點，所以在實際運用中間，我們這個Merge_sort基本上不被用於做內排序，就如果我們所有的元素都可以在內存裡面完成，這個時候沒人用歸併排序去做這件事，歸併排序在什麼情況下特別有用呢？就是在外排序的時候，它是一個非常有用的工具。