歸併排序演算法

歸併排序是一種基於分治技術的排序技術。其最壞時間複雜度為Ο(n log n)，是使用最廣泛和最受青睞的演算法之一。

歸併排序首先將陣列分成相等的兩半，然後以排序的方式將它們合併。

歸併排序是如何工作的？

為了理解歸併排序，我們以一個未排序的陣列為例：

我們知道歸併排序首先迭代地將整個陣列分成相等的兩半，直到達到原子值。這裡我們看到一個包含8個元素的陣列被分成兩個大小為4的陣列。

這不會改變元素在原始陣列中的出現順序。現在我們將這兩個陣列分成兩半。

我們進一步劃分這些陣列，並獲得無法再劃分的原子值。

現在，我們將它們以與分解時完全相同的方式合併。請注意給這些列表提供的顏色程式碼。

我們首先比較每個列表的元素，然後以排序的方式將它們合併到另一個列表中。我們看到14和33處於排序位置。我們比較27和10，在目標列表的2個值中，我們首先放置10，然後是27。我們改變19和35的順序，而42和44按順序放置。

在合併階段的下一輪迭代中，我們比較兩個資料值的列表，並將它們合併到一個已找到資料值的列表中，並將所有資料按排序順序放置。

最終合併後，列表變為排序狀態，並被認為是最終解決方案。

歸併排序演算法

歸併排序不斷將列表分成相等的兩半，直到無法再劃分。根據定義，如果列表中只有一個元素，則認為它是已排序的。然後，歸併排序合併較小的已排序列表，同時保持新列表也已排序。

Step 1: If it is only one element in the list, consider it already 
sorted, so return.
Step 2: Divide the list recursively into two halves until it can no  
more be divided.
Step 3: Merge the smaller lists into new list in sorted order.

虛擬碼

現在我們將看到歸併排序函式的虛擬碼。正如我們的演算法指出的那樣，有兩個主要函式——劃分和合並。

歸併排序使用遞迴，我們將以相同的方式檢視我們的實現。

procedure mergesort( var a as array )
   if ( n == 1 ) return a
      var l1 as array = a[0] ... a[n/2]
      var l2 as array = a[n/2+1] ... a[n]
      l1 = mergesort( l1 )
      l2 = mergesort( l2 )
      return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   return c
end procedure

示例

在下面的示例中，我們逐步展示了歸併排序演算法。首先，每次迭代陣列都被分成兩個子陣列，直到子陣列只包含一個元素。當這些子陣列無法進一步劃分時，執行合併操作。

分析

讓我們考慮一下歸併排序的執行時間為T(n)。因此，

$$\mathrm{T\left ( n \right )=\left\{\begin{matrix} c & if\, n\leq 1 \\ 2\, xT\left ( \frac{n}{2} \right )+dxn &otherwise \\ \end{matrix}\right.}\:其中\: c\: 和\: d\: 是\: 常數$$

因此，使用此遞迴關係，

$$T\left ( n \right )=2^{i}\, T\left ( n/2^{i} \right )+i\cdot d\cdot n$$

$$由於,\:\: i=log\: n,\: T\left ( n \right )=2^{log\, n}T\left ( n/2^{log\, n} \right )+log\, n\cdot d\cdot n$$

$$=c\cdot n+d\cdot n\cdot log\: n$$

$$因此,\: \: T\left ( n \right ) = O(n\: log\: n ).$$

示例

以下是上述方法在各種程式語言中的實現：

#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high){
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)
      b[i++] = a[l1++];
   while(l2 <= high)
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
}
void sort(int low, int high){
   int mid;
   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   } else {
      return;
   }
}
int main(){
   int i;
   printf("Array before sorting\n");
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
   sort(0, max);
   printf("\nArray after sorting\n");
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
}

Array before sorting
10 14 19 26 27 31 33 35 42 44 0 
Array after sorting
0 10 14 19 26 27 31 33 35 42 44 

#include <iostream>
using namespace std;
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high){
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)
      b[i++] = a[l1++];
   while(l2 <= high)
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
}
void sort(int low, int high){
   int mid;
   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   } else {
      return;
   }
}
int main(){
   int i;
   cout << "Array before sorting\n";
   for(i = 0; i <= max; i++)
      cout<<a[i]<<" ";
   sort(0, max);
   cout<< "\nArray after sorting\n";
   for(i = 0; i <= max; i++)
      cout<<a[i]<<" ";
}

Array before sorting
10 14 19 26 27 31 33 35 42 44 0 
Array after sorting
0 10 14 19 26 27 31 33 35 42 44 

public class Merge_Sort {
   static int a[] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
   static int b[] = new int[a.length];
   static void merging(int low, int mid, int high) {
      int l1, l2, i;
      for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
         if(a[l1] <= a[l2])
            b[i] = a[l1++];
         else
            b[i] = a[l2++];
      }
      while(l1 <= mid)
         b[i++] = a[l1++];
      while(l2 <= high)
         b[i++] = a[l2++];
      for(i = low; i <= high; i++)
         a[i] = b[i];
   }
   static void sort(int low, int high) {
      int mid;
      if(low < high) {
         mid = (low + high) / 2;
         sort(low, mid);
         sort(mid+1, high);
         merging(low, mid, high);
      } else {
         return;
      }
   }
   public static void main(String args[]) {
      int i;
      int n = a.length;
      System.out.println("Array before sorting");
      for(i = 0; i < n; i++)
         System.out.print(a[i] + " ");
      sort(0, n-1);
      System.out.println("\nArray after sorting");
      for(i = 0; i < n; i++)
         System.out.print(a[i]+" ");
   }
}

Array before sorting
10 14 19 26 27 31 33 35 42 44 0 
Array after sorting
0 10 14 19 26 27 31 33 35 42 44

def merge_sort(a, n):
   if n > 1:
      m = n // 2
      #divide the list in two sub lists
      l1 = a[:m]
      n1 = len(l1)
      l2 = a[m:]
      n2 = len(l2)
      #recursively calling the function for sub lists
      merge_sort(l1, n1)
      merge_sort(l2, n2)
      i = j = k = 0
      while i < n1 and j < n2:
         if l1[i] <= l2[j]:
            a[k] = l1[i]
            i = i + 1
         else:
            a[k] = l2[j]
            j = j + 1
         k = k + 1
      while i < n1:
         a[k] = l1[i]
         i = i + 1
         k = k + 1    
      while j < n2:
         a[k]=l2[j]
         j = j + 1
         k = k + 1

a = [10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0]
n = len(a)
print("Array before Sorting")
print(a)
merge_sort(a, n)
print("Array after Sorting")
print(a)

Array before Sorting
[10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0]
Array after Sorting
[0, 10, 14, 19, 26, 27, 31, 33, 35, 42, 44]