Merge Sort

Merge sort divides the array in half, sort each of those halves, and then merge them back together.

核心：将两个有序对数组归并成一个更大的有序数组。通常做法为递归排序，并将两个不同的有序数组归并到第三个数组中。

复杂度分析

平均情况与最坏情况均为 $O(n*logn)$，空间复杂度为 $depends$.