歸并算法定義：所謂歸并排序是指將兩個或兩個以上有序的數列（或有序表），合并成一個仍然有序的數列（或有序表）。

這樣的排序方法經常用于多個有序的數據文件歸并成一個有序的數據文件。

歸并排序相比較之前的排序算法而言加入了分治法的思想，其算法思路如下：

1.如果給的數組只有一個元素的話，直接返回（也就是遞歸到最底層的一個情況）

2.把整個數組分為盡可能相等的兩個部分（分）

3.對于兩個被分開的兩個部分進行整個歸并排序（治）

4.把兩個被分開且排好序的數組拼接在一起

代碼演示如下：

void merge(int arr[], int l, int m, int r) 
{ int i, j, k; int n1 = m - l + 1; int n2 =  r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1+ j]; i = 0; j = 0; k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else{ arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } 
} void mergeSort(int arr[], int l, int r) 
{ if (l < r) { int m = l+(r-l)/2; mergeSort(arr, l, m); mergeSort(arr, m+1, r); merge(arr, l, m, r); } 
} 

?

?