核心思想：假设数组前后两部分各自有序，然后各定义两个指针，谁小谁放到新开辟的数组里面，最后把新开辟的数组赋值给原数组就完成了。要使前后两部分有序就采用递归的方式，不断往下划分块，最后一层划分为两个元素一组或者一个元素一组，这样一层一层地往上递归排序，就实现了整个有序。

注意：以下的分块方法会出现问题，[2,3]这个区间一直存在，会死循环，进而栈溢出

解决办法，改变分割区间的方法：

// 17:13
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;// 如果[begin, mid][mid+1, end]有序就可以进行归并了_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid+1, end);// 归并int begin1 = begin, end1 = mid;int begin2 = mid+1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while(begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a+ begin, tmp+ begin, (end - begin + 1) * sizeof(int));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}

时间复杂度：O(N*logN)  因为是递归，递归了logN层（二叉树高度），每一层比较N次。

空间复杂度：O(N)  多开辟了tmp数组的空间。