?归并排序算法
归并排序的基本思路就是“分治法”：
（1）分割：将数组对半分割，并在分割后的子数组中继续递归的对半分割；
（2）治理（解决）：分割到子数组只有一个元素的时候，可看作是有序；
（3）合并：从下往上，将有序的子数组两两合并，最终使整个数组有序；
时间复杂度：O(NlogN)为平均复杂度，时间复杂度取值区间实际为[O(N),O(NlogN)]
空间复杂度：O(N)对于递归版，除了单独的数组空间，还有递归的空间logN，递归版的实际空间复杂度为O(N+logN)
稳定性：稳定
一般认为，归并排序效率低于快速排序，虽然二者平均时间复杂度相同，且复杂度区间来看归并排序波动更小，但实际情况来看，快速排序，在连续内存的数组上效率要优于归并排序，而归并排序在链表数组上效率优于快速排序。归并排序中，最后的合并开销不可忽略，随着问题规模的增大，合并开销对效率的影响也越明显。但归并排序是稳定排序，通常情况下会选择快速排序，而当有稳定性需求时，就可以选择归并排序了。此外，如果能确认数组本身是基本有序的，可以用归并排序算法。代码链接（MergeSort.cpp）：