例子： 5 2 1 6 4 7 9 0 8 3
思路： 1.采用分治算法：将一个大区间，不断划分成小区间。当区间中只有一个数时，对于该区间肯定是有序的，当区间中没有数时，区间也是有序的。 2.申请一块额外的空间用来存储排序后的内容。 3.将有序的小区间进行合并，保存到新申请的空间内。步骤：1.申请空间，申请的空间大小为两个已经排序序列之和 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素，选择相对小的元素放到合并空间内， 并且移动指针到下一位置 4.重复上一步，知道都已指针到达序列尾 5.将另一序列剩下的所有元素直接复制到合并序列尾
时间复杂度： O(nlogN) 分治算法，所以是logN
空间复杂度: O(n)
void Merge(int arr[], int left, int mid,int right, int extra[]) { //两个区间 [left,mid] [mid,right] int left_Index = left; //左边区间的下标 int right_Index = mid+1; //右边区间的下标 int extra_Index = left; //extra的下标 //合并两个有序数组 while (left_Index <= mid && right_Index <= right) { if (arr[left_Index] <= arr[right_Index]) extra[extra_Index++] = arr[left_Index++]; else extra[extra_Index++] = arr[right_Index++]; } //将还有剩余元素的数组放到extra中 while (left_Index <= mid ) { extra[extra_Index++] = arr[left_Index++]; } while (right_Index <= right) { extra[extra_Index++] = arr[right_Index++]; } for (int i = left; i <= right; i++) { arr[i] = extra[i]; } return; } void _MergeSort(int arr[], int left,int right, int extra[]) { if (left == right) { //小区间中只有一个元素 return; } if (left > right) { //小区间中没有元素 return; } int mid = left + (right - left) / 2; //如果left == 0 right == 1,那么mid==0,如果对mid-1,数组下标就会出现负数，因此最好不要向前减小 /*_MergeSort(arr,left,mid-1,extra); //注意分组,划分小区间。 注意！！！！在数组中，最好让数组下标往后越界，不要往前越界， 因为arr[-1] arr[11]差别还是很大的 _MergeSort(arr, mid, right, extra); */ _MergeSort(arr,left,mid,extra); _MergeSort(arr, mid+1, right, extra); //合并两个有序数组 Merge(arr,left,mid,right,extra); } void MergeSort(int arr[], int size) { int *extra = (int*)malloc(40); _MergeSort(arr,0,size-1,extra); //采用了左闭右闭 free(extra); }