[[338250]]

今天分享的的內容涉及以下兩個問題：

1. 歸并排序的迭代實現方式;
2. 實現一個原地歸并排序(In-Place Merge Sort);

歸并排序的迭代實現

在正式看代碼前，希望你心中清楚歸并排序的遞歸實現方式，不熟悉也無妨，看這篇文章 圖解「歸并排序」算法(修訂版) 文章。

迭代和遞歸(Iteration & Recursion)本就心心相惜，你中有我，我中有你，任何一個算法的遞歸實現都可以將其變成一個迭代的實現方式，只要代價足夠小，收益(獲得的空間和時間效率的提升)足夠高就可以。

歸并排序同樣可以做到，只是歸并排序的迭代實現方式較為特殊，不像大多數遞歸與迭代的轉化，歸并排序并不需要程序中出現一個顯式的 stack 輔助棧，但同樣能夠去掉遞歸調用，以迭代的方式實現歸并排序。

這張圖一定很熟悉了，這就是標準的遞歸實現過程中的分與治，而采用迭代實現時，策略上有兩點發生了變化：

1. 分的方式采用循環(迭代)，而不是遞歸的方式;
2. 分的策略和遞歸的方式有別，依舊符合歸并排序的思想;

我們依舊以下面的數組為例說明(感覺這個數組萬能，哈哈)：

第一步：合并 5 和 1

第二步：合并 4 和 2

第三步：合并 8 和 4 ;

第四步：合并 [1,5,2,4]

第五步：合并 [4,8]

第六步：合并 [1,2,4,5,4,8]

看到這里，并不能清晰地看出歸并排序迭代和遞歸之間的差異，客官莫急：

這次就會清晰可見了，歸并排序的迭代實現方式中的合并順序與遞歸明顯不同，遞歸是將長度為 n 的原始數組一分為二，然后再將兩個(1/2)的數組再一分為二，直到分為n個長度為1的元素。然后兩兩按大小合并，如此反復，直到最后形成包含 n 個數的一個有序數組。

而迭代就不同了，默認將數組當中的元素當做 n 個長度為1的元素;依次按照 2 個一組合并，4 個元素為一組進行合并(不足 4 個，比如 [4,8] ，不足 4 個就按照剩余個數 2 合并)，....，最后以 n/2 個元素為一組進行合并，得到我們的有序數組。

迭代實現中，僅從圖中似乎看不到分的過程，但事實上，合并前已經進行了分，只不過這個分與遞歸調用的分不同，而是采用迭代。

忽略合并的實現細節，我們僅看一下迭代的實現方式。

static void mergeSort(int arr[], int n)  
{  
  
    int curr_size; //標識當前合并的子數組的大小，從 1 已知到 n/2 
    int left_start; //標識當前要合并的子數組的起點 
    for (curr_size = 1; curr_size <= n-1; curr_size = 2*curr_size)  
    {  
        for (left_start = 0; left_start < n-1; left_start += 2*curr_size)  
        {  
            int mid = Math.min(left_start + curr_size - 1, n-1);  
  
            int right_end = Math.min(left_start + 2*curr_size - 1, n-1); 
    
            merge(arr, left_start, mid, right_end); 
         }  
     }  
}  
//合并略 

歸并排序的迭代實現就是將遞歸中 遞 的操作修改成了兩層的 for 循環，為了理解這兩層循環所進行的操作，建議最好自己將數組 [5,1,4,2,8,4] 代進去手動的計算一遍，下圖中給出了merge(arr, left_start, mid, right_end); 函數依次調用數據：

請問如何用迭代實現三路歸并排序?

答案很簡單了，將上面提供的二路歸并排序的迭代實現中的所有 2 替換為 3，合并過程將變成下圖：

改日再詳述 3 路歸并排序，接著看第二個問題。

原地歸并排序

所謂原地排序(In-place Sort)就是空間復雜度為的排序算法。圖解「歸并排序」算法(修訂版) 中所講的歸并排序空間復雜度為，時間復雜度為，其中的空間復雜度是由 merge(arr, left, mid, right) 函數所造成的，所以關于這個問題的解決就是折騰 merge 函數。

該如何折騰呢?看栗子(哈哈，就是廢話少)。

同樣以最后一次合并為例：

這里的 start1 、start2 還有 mid 的初始設置就不多說了，看原地合并過程即可。

第一步：比較 start1 指向的元素 1 和 start2 指向的元素 2 ，1 < 2 ，所以直接將 start1右移，即 start1++ .

第二步：比較 start1 指向的元素 4 和 start2 指向的元素 2 ，4 > 2 ，此時不使用額外空間實現合并操作，將 start2 之前，start1 (包含 start1) 之后的元素向后移動，并將 2 拷貝到 start1 所指向的位置，然后將 start1 、start2 還有 mid 均向后移動：

第三步：比較 start1 指向的元素 4 和 start2 指向的元素 4 ，4 = 4 ，所以直接將 start1右移，即 start1++ .

第四步：與第二步類似，比較 start1 指向的元素 5 和 start2 指向的元素 4 ，5 > 4 ，將 4向前移動，將 5 向后移動，然后將 start1 、start2 還有 mid 均向后移動：

第五步：比較 start1 指向的元素 5 和 start2 指向的元素 8 ，**5 < 8 ** ，直接將 start1右移，即 start1++ ;此時 start1 > mid ,表明合并完成了。

空間復雜度為 的合并操作的實現代碼：

static void merge(int arr[], int start1, int mid, int end){ 
    int start2 = mid + 1; 
     
    //如果 mid 小于等于 mid+1 的元素，表明數組已經有序，不需要合并 
    if(arr[mid] <= arr[start2]){ 
        return; 
    } 
     
    while(start1 <= mid && start2 <= end){ 
        if(arr[start1] <= arr[start2]){ 
            start1++; 
        } 
        else{ 
            int value = arr[start2]; 
            int index = start2; 
             
            //將 [start1,start2 - 1]中的元素向后移動 
            while(index != start1){ 
                arr[index] = arr[index - 1]; 
                index--; 
            } 
             
            arr[start1] = value; 
             
            start1++; 
            mid++; 
            start2++; 
        } 
    } 
} 

注意這個合并操作中涉及到了兩個嵌套的 while 循環，所以與空間復雜度為，時間復雜度為的標準實現相比，這種合并策略雖然將空間復雜度降到了 ，但同時也犧牲了時間復雜度，時間復雜度變成了

時間復雜度和空間復雜度就似陰陽之術，得失之理，生死之界;要得其一，必失其一，這個世上沒有兩全其美的事情!

  本文轉載自微信公眾號「景禹」，可以通過以下二維碼關注。轉載本文請聯系景禹公眾號。