算法原理：归并排序的思想是分治，将一个带排序的数组分成两个较小的数组，然后分别进行排序，组后将两个排好序 的较小的数组合并起来，就得到了原来数组的排序后的结果。应该注意的是这种将两个排好序的数组合并有一个较好的算法，时间复杂度是O(n1+n2)的。 n1、n2分别是两个小数组的长度。
算法代码：
#include <iostream> using namespace std; void merge_sort(int *arr,int start,int end,int *temp) { if(end > start+1) { int mid = start + (end - start) / 2; merge_sort(arr,start,mid,temp); merge_sort(arr,mid,end,temp); int i = start , j = mid , k = start; while(i < mid || j < end) { if(j >= end || (i < mid && arr[i] <= arr[j])) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } for(i = start ; i < end ; ++i) { arr[i] = temp[i]; } } } int main() { int temp[8]; int arr[] = {2,1,4,3,8,7,5,6}; merge_sort(arr,0,8,temp); for(int i = 0 ; i < 8 ; ++i) { cout<<arr[i]<<" "; } cout<<endl; return 0; }
小结：归并排序时稳定的排序，但是不属于原地排序，因为用了额外的O(n)的空间，时间复杂度降到了O(n*log n)，并且对任意的数组进行排序时间复杂度都能控制在O(n*logn)。
