时间复杂度

• 平均 O(nlogn)
• 最佳 O(nlogn)
• 最坏 O(nlogn)

空间复杂度

不是原地排序，有个结果数组。

• 平均 O(n)
• 最佳 O(n)
• 最坏 O(n)

核心思想：分治法 (Divide and Conquer) + 合并 (Merge)

归并排序的思路更加纯粹：它不断地将一个大数组对半拆分，直到每个子数组都只剩下一个元素（单个元素天然是有序的）。然后，再反过来，将这些有序的子数组两两合并，最终合并成一个完整的有序数组。