本文共 1072 字，大约阅读时间需要 3 分钟。

思路：
每次把数组分成两部分，一直递归下去，当分成最少长度后，开始从最底层向上归并相邻的两段数组。时间复杂度O（n log n）。

代码：

#include <iostream>#include <algorithm> #include <cstdio> using namespace std;void merge(int a[], int left, int right, int mid){   	int tmp[right-left+1], i, j, k;	for (k=left; k<=right; k++)		tmp[k-left]=a[k];	i=left;	j=mid+1;	for (k=left; k<=right; k++){   		//如果一个较先完成后，剩下的那一部分就直接拷贝过去，需要提前判断 		if (i>mid){   //mid属于左侧那一半 			a[k]=tmp[j-left];			j++;		}else if (j>right){   			a[k]=tmp[i-left];			i++;		}else if (tmp[i-left]>tmp[j-left]){   			a[k]=tmp[j-left];			j++;		}else{   			a[k]=tmp[i-left];			i++;		}	}}void merge_sort(int a[], int left, int right){   	if (left>=right)			return;	int mid=(left+right)/2;	merge_sort(a, left, mid);//递归 每次将区间分成两块 	merge_sort(a, mid+1, right);	merge(a, left, right, mid);//从最低层向上归并 	return;}void mergesort(int a[], int left, int right){   	merge_sort(a, left, right-1);//左闭右开数组区间 }int main(){   	int a[105], n;	scanf("%d", &n);	for (int i=0; i<n; i++)		scanf("%d", &a[i]);	mergesort(a, 0, n);//下标从零开始 左闭右开	for (int i=0; i<n; i++)		printf("%d ", a[i]);	return 0;}