归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 主要思路： 当排序一个数组的时候，归并排序首先将这个数组分成一半，然后把左边的数组给排序，右边的数组给排序，之后再将它们归并起来；当对左边的数组和右边数组进行排序的时候，再分别将左边的数组和右边的数组分成一半，然后对每一个部分先排序，再归并。对于上面的每一个部分，依然是先将他们分半，再归并，分到一定细度的时候，每一个部分就只有一个元素了，那么此时不用排序，对他们进行一次简单的归并就好了。归并到上一个层级之后继续归并，归并到更高的层级，直至最后归并完成。 核心代码如下：
#include <iostream> #include <algorithm> using namespace std; void __merge(int* arr, int l, int mid, int r){ int* aux = new int[r - l + 1]; //aux数组为辅助空间 for(int i = l; i <= r; i++){ aux[i - l] = arr[i]; } int i = l, j = mid + 1; for(int k = l; k <= r; k++){ if(i > mid){ arr[k] = aux[j - l]; j++; } else if(j > r){ arr[k] = aux[i - l]; i++; } else if(aux[i - l] < aux[j - l]){ arr[k] = aux[i - l]; i++; } else{ arr[k] = aux[j - l]; j++; } } delete[] aux; } void __mergeSort(int* arr, int l, int r){ if(l >= r) return; int mid = (l + r) / 2; __mergeSort(arr, l, mid); __mergeSort(arr, mid + 1, r); __merge(arr, l, mid, r); } void mergeSort(int* arr, int n){ __mergeSort(arr, 0, n - 1); } int main(){ int arr[] = {8,5,2,4,6,3,1,7}; int length = sizeof(arr) / sizeof(arr[1]); mergeSort(arr, length); for(int i = 0; i < length; i++) cout << arr[i] << " "; cout << endl; return 0; }