归并排序算法：
思路，设置left,mid,right三个参数，对mid的左和右分别再进行递归调用归并排序算法，直到每个数组中只有1时返回，最终完成归并排序，具体思路见程序
注：归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n+logn)。
代码实现：
//归并排序（排序后为从小到大）#include <iostream> #include <algorithm> using namespace std; void Merge(int *data, int left, int mid, int right){int *temp = new int[right - left + 1];//new一个temp保存归并后的数据int ind = 0, i = left, j = mid + 1;while (i <= mid&&j <= right){//将两个待归并的数据进行比较存入，注意边界值temp[ind++] = (data[i] < data[j]) ? data[i++] : data[j++];}while (i <= mid){//将一个数组中剩余的数据存入temp[ind++] = data[i++];}while (j <= right){temp[ind++] = data[j++];}for (int i = left; i <= right; ++i){//将temp中的数据放到data里data[i] = temp[i - left];}delete[] temp;}void MSort(int *data, int left, int right){//递归实现归并排序if (left >= right) return;else{int mid = left + (right - left) / 2;MSort(data, left, mid);//分别对左右进行归并排序MSort(data, mid + 1, right);Merge(data, left, mid, right);}}int main(){ int a[] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };cout << "before sorted:" << endl;for (size_t i = 0; i < 9; ++i){//输出 cout << a[i] << " ";}cout << endl;int a_size = sizeof(a) / sizeof(a[0]);int *p = a;MSort(p,0,a_size-1);cout << "after sorted:" << endl;for (size_t i = 0; i < 9; ++i){//输出cout << p[i] << " ";}cout << endl; return 0;}
程序输出：
