前言：前面我們的排序已經詳細的講解了一系列的方法，那么我們現在久之后一個歸并排序了，所以我們現在就來講解一下歸并排序。

歸并排序：

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and
Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有
序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid][mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);// [begin, mid][mid+1, end]歸并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

a是我們待排序的數組，里面存放了要排序的數據，tmp是我們額外開辟的數組用來存放我們排好序的數據，而我們排好序的數據則是像鏈表一樣尾插入數組的。我們先找出中間值，給這個區間分成兩個小區間，兩個小區間各自在分成小區間。從左到右逐一比較兩個小區間中的元素，把較小的元素優先放入額外開辟的數組tmp，如果一個小區間的全部尾插到tmp中就結束了循環，而另外一個數組則按順序的尾插到tmp中。最后我們的tmp中的數據拷貝到數組a中就完成了。

void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

這里就是用來開辟額外數組tmp的，我們傳參到函數_MergeSort，在_MergeSort中遞歸完成排序之后就返回，再將開辟的空間銷毀。

如果最大家有所幫助的話就支持一下吧！感謝大家！