MergeSort 講解 ( Recursive and Iterative)

論壇上 已經有同學寫了 Bubble, insertion, selection, quick, shell 五種排序算法了，如下鏈接：
http://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=199

我看了之後覺得很有用，所以自己再寫個 MergeSort 吧，作為以上5種排序的補充。

如果有疑問，或者有更快速更簡便的方法，希望大家提意見。

MergeSort is a very typical algorithm which uses Divide and Conquer.  The hard problem in this algorithm is that,for two already sorted arrays, how can you merge them into a new sorted arrayin linear time? Assume that the a[0…3] is a sorted array, and a[4…8] is another sorted array.

index	0	1	2	3	4=middle	5	6	7	8
value	11	13	14	18	10	12	15	17	18

We want to merge them so that a[0…8] will be  

index	0	1	2	3	4=middle	5	6	7	8
value	10	11	12	13	14	15	17	18	18

現在開始merge，
算法就是比較 a[0…3] 中最小值和 a[4….8]中最小值，最開始 i=0, j=4，比較11 和10，

index	i=0	1	2	3	j=4	5	6	7	8
value	11	13	14	18	10	12	15	17	18

10<11,把10移動到 臨時的空間 temp[0...8]裡面。然後 j向右移動，j=5, 再比11 和 12，

index	i=0	1	2	3	4	j=5	6	7	8
value	11	13	14	18		12	15	17	18

11<12, 把11移到temp[0...8]裡面，i向右移動， i=1

index	0	i=1	2	3	4	j=5	6	7	8
value		13	14	18		12	15	17	18

再比13和 12，把12移走，再比13 和 15，把13移走… 最後 temp[0...8]就是排好序的了

So we have a function

void merge(int a[], int middle, int n)
/*
Where “a” is a sorted array whose length is “middle”, and “ a+middle” is another sorted array whose length is “n-middle”. Our goal is to sort them into a single array “a”，上表格中 middle =4 , n=9
*/
{

   // k from 0 to n
   // i from 0 to middle , j from middle to end
   int i, j, k;
   if(n <= middle) return;

   int *temp = (int*) malloc(sizeof(int) * n);

   for( i = 0, j = middle,k=0 ; i < middle && j < n ; k++) {
      if(a[ i ] < a[j])
         temp[k] = a[i++];
      else
         temp[k] = a[j++];
   }

   while(i < middle)  temp[k++] = a[i++];
   while(j < n)       temp[k++] = a[j++];

   for(k = 0; k < n; k++) {
      a[k] = temp[k];
   }
   free(temp);
   /* 這種寫法 需要不停地 malloc, 會影響程序的速度，我們可以給此函數加一個參數，把臨時空間放在此函數的外面，既在此函數外面 調用malloc ，這樣就只用調用malloc 一次了， 具體的代碼實現 會影響程序的可讀性，所以我在這裡就不寫了。*/

}


由於需要臨時空間temp[0…n]，MergeSort要用到 O(n)空間，我曾經想過， In-place merge sort有沒有可能？
我曾經寫的In-place merge， 代碼如下：

void mergeWithoutExtraSpace(int a[], int middle, int n)
{
   // a = array
   // num1 = number of elements in the first half array
   // num2 = ......................... second .........

   int *k;
   int temp;
   int *b;
   int num1= middle;
   int num2 = n - num1;

   b = a + num1; // b points to the second half array

   while(num1 > 0 && num2 > 0) {
      if(*b < *a) {
         temp = *b;
         for(k = b; k > a; k--) {
            *k = * (k - 1);   // use insertion which is O(n^2)
         }
         *a = temp;
         b++;
         num2--;
      } else {
         num1--;
      }
      a++;
   }
}

上面的 mergeWithoutExtraSpace 函數 用了 插入法 。雖然 比較的次數仍然是O(n), 但 插入需要O(n^2)。  
所以 This version above saves space but uses O(n^2) time ! Do not use it for merge sort!

下面就開始正式 mergesort了。
原理是 把一個array從中間分成左右兩份，左邊排序，右邊排序，然後 merge，就成功了。
Recursion 和 iteration 都可以實現 mergesort ， 下面分開介紹：

Recursive寫法 ：
void mergeSortRecursive(int a[], int n)  
//a 是 array， n是array的長度，halflength 是 平均分割後左邊的長度。
{
   int halfLength;

   if(n <= 1) return;
   halfLength = n / 2;

   mergeSortRecursive(a, halfLength); //左邊排序
   mergeSortRecursive(&a[halfLength], n - halfLength); //右邊排序
   merge(a, halfLength, n);  // 合成兩個已經排好的
}
Recursive 不難，就不用多說了。

Iterative 寫法：
void mergeSort(int a[], int n)
{
#define min(a,b) ((a)<(b)?(a):(b))

   int i, j;

   // 2*i is the length of merged result

   for(i = 1; i < n; i *= 2) {
      for(j = 0;  j < n ; j += 2 * i) {         
         merge(a + j, min(i,n-j) , min(2 * i,n-j) ); // 用 min(i,n-j) , 是因為最後一個 element 不能超出 array 邊界。
      }
   }
}

index	0	1	2	3	4	5	6	7	8
i=1	j		j		j		j		j
i=2	j				j				j
i=4	j								j
i=8	j

當i=1時，j 的位置是 0,2,4,6,8，array 中的元素 一個一個組合，合成後的長度為2 。但最後一個 a[8] 無法配對。
當i=2時，j 的位置是 0,   4,   8,  array 中的元素 兩個兩個組合，合成後的長度為4。 但最後一個 a[8] 無法配對。

但以上的代碼有2個缺陷：
1. 每次 j 循環 都要判斷 merge的 是不是最後一個 元素 a[8]，如果是 則取min(i,n-j)
2. 每次 i 循環 都調用 merge (&a[8],1,1), 而a[8] 已經被merge好了，並不需要額外的調用。

我們改進一下：
由於最後一個array的長度不定， 在 j 循環的最後一次，( 遇到 a[8] 時），我們應該直接跳出循環，  單獨處理 最後一個 element。修改後最終如下：  

void mergeSort(int a[], int n)
{
   int i, j;
   int halflength,length;

   // 2*i is the length of merged result
   for(i = 1; i < n; i *= 2) {
      for(j = 0;  j < n - 2 * i ; j += 2 * i) {
         // the last element has variable size. Leave it unmerged
         merge(a + j, i , 2 * i);
      }

      // The range of j is between [n-2i,n)
      // Merge the last element in the array

      if(i<n-j) {
         merge(a + j, i ,n-j);
      }
   }
}

先顶再看。。。看起来牛爆了的样子。。

列宾 发表于 2012-12-29 09:59
先顶再看。。。看起来牛爆了的样子。。

我是来赞你头像的

过多的malloc和free对运行时间不利。 可以之前就启用临时数组temp, 最后销了。

建议Iterative 写法需要更详尽的解释~

写得不错！