1?算法核心思想
歸并排序是一種高效的排序方式，需要用到遞歸來實現，我們先來看一下動圖演示：
算法核心思想如下：
1.將數組盡量平均分成兩段。
2.將這兩段都變得有序（使用遞歸實現）。
3.將兩段合并。
2 代碼實現
首先，我們先定義一個歸并排序的函數，里面接受三個參數：
void MergeSort(int arr[], int left, int right) {}arr代表需要進行排序的數組，left表示數組arr的最左端點，right表示數組arr的最右端點。
首先我們需要把數組分成兩段，我們可以用二分的方法：
int mid = (left + right) >> 1;這里右移（>>為右移運算符）1為和除以2含義相同。
也可以用防溢出，因為left+right的值可能會爆int，導致結果錯誤：
int mid = left + (right - left) >> 1;然后對兩段分別進行遞歸，第一段是[1, mid]，第二段是[mid+1, right]：
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);由于我們需要對數組進行操作，但是直接在arr操作可能會導致原始數據丟失，但是如果再創建一個數組會占用內存，所以我們可以向電腦“租借”right-left+1個空間，用關鍵字new來完成：
int* tmp = new int[right - left + 1];注意要以指針的形式定義。
由于我們要把數組變得有序，而我們歸并排序的思想就是分而治之，然后再依次變得有序，需要用到分治的思想。那么我們先定義一些變量：
int cur = 0, cur1 = left, cur2 = mid + 1;cur為tmp數組的元素下標，cur1為第一段的最左端點，cur2為第二段的最左端點。
然后我們對tmp數組和arr數組進行循環操作，這里可以用while循環，循環條件是cur1<=mid&&cur2<=right。
如果arr[cur1]比arr[cur2]更大，那么就先把arr[cur2]放回tmp，否則放arr[cur1]。
代碼：
while(cur1 <= mid && cur2 <= right)
{if(arr[cur1] < arr[cur2])tmp[cur++] = arr[cur1++];elsetmp[cur++] = arr[cur2++];
}然后處理可能有的數組殘余未處理的部分：
while(cur1 <= mid)tmp[cur++] = arr[cur1++];
while(cur2 <= right)tmp[cur++] = arr[cur2++];然后合并數組，方法跟處理時差不多的：
for(int i = 0; i < right - left + 1; i++)arr[left + i] = tmp[i];就是把tmp的元素依次賦值給arr。
最有我們需要把tmp的空間還給內存，所以我們delete一下：
delete[] tmp;然后我們的arr就變的有序了。
但是，如果這樣寫，程序就成功被我們干崩了，因為我們忘記寫遞歸出口了，補一個遞歸出口：
if(left == right)return;我們合并一下整段代碼：
void MergeSort(int arr[], int left, int right) {if(left == right)return;int mid = (left + right) >> 1;MergeSort(arr, left, mid);MergeSort(arr, mid + 1, right);int* tmp = new int[right - left + 1];int cur = 0, cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){if(arr[cur1] < arr[cur2])tmp[cur++] = arr[cur1++];elsetmp[cur++] = arr[cur2++];}while(cur1 <= mid)tmp[cur++] = arr[cur1++];while(cur2 <= right)tmp[cur++] = arr[cur2++];for(int i = 0; i < right - left + 1; i++)arr[left + i] = tmp[i];delete[] tmp;
}3 算法時間復雜度
正常情況下，歸并排序時間復雜度為：
O(NLogN)
再見！
)
