归并排序利用分治法将数组对半分割，递归排序子数组，最后合并排序后的子数组。其时间复杂度在最好、最坏和平均情况下均为 $O(n \log n)$，但需要额外的 $O(n)$ 空间来合并子数组。