算法思想
数组排序任务可以如下完成：
1)把前一半排序
2)把后一半排序
3)把两半归并到一个新的有序数组，然后再拷贝回原数组，排序完成。
时间复杂度：o(nlogn),空间复杂度o(n)
（在前一半的排序中，又用到了归并算法，一直再分，直到待排序数组只有一个元素，因此归并排序需要用到递归来实现）
程序代码
#include<iostream>using namespace std;#define MAXSIZE 10//归并排序需要额外的一个数组来存储中间结果 int a[100],b[100];//归并的过程中需要使用额外的存储空间来完成排序 void merge(int start,int mid,int end){//将数组a的局部a[s,m]和a[m+1,e]合并到b,并保证b有序，然后再拷贝回a[s,m] //归并操作时间复杂度:O(n) //我们为两个待归并的序列，各设一个指针，为我们的中转序列也设一个指针，都指向其开头 int i=start,j=mid+1,m=start;//看哪个指针所指向的值更小，如果小的话，我们就复制到目标数组中去，并且指针需要往后移 while(i<=mid&&j<=end){if(i<=mid&&a[i]<=a[j]){b[m++]=a[i++];} if(j<=end&&a[i]>a[j]){b[m++]=a[j++];} }//当上面的循环走完了之后，有一个指针会走到终点，接下来把另一个指针也走到终点 while(i<=mid){b[m++]=a[i++];}while(j<=end){b[m++]=a[j++];}for(int i=start;i<=end;i++){a[i]=b[i];}}void mergeSort(int start,int end){//实际上，递归的终止条件就是s不小于e。只有s<e的时候再做排序 if(start<end){int mid=(start+end)/2;//将s和e分成两半 mergeSort(start,mid);//前一半做排序 mergeSort(mid+1,end);//后一半做排序 merge(start,mid,end);//归并，将两个有序的序列归并到一起。 }}int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];} mergeSort(0,n-1);for(int i=0;i<n;i++){cout<<b[i]<<" ";} return 0;}
时间复杂度分析
时间复杂度O(nlogn)
