相关力扣题：排序数组

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

算法步骤

归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：

  1. 如果输入内只有一个元素，则直接返回，否则将长度为 n 的输入序列分成两个长度为 n/2 的子序列；

  2. 分别对这两个子序列进行归并排序，使子序列变为有序状态；

  3. 设定两个指针，分别指向两个已经排序子序列的起始位置；

  4. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；

  5. 重复步骤 3 ~ 4 直到某一指针达到序列尾；

  6. 将另一序列剩下的所有元素直接复制到合并序列尾。

图解算法

MergeSortMergeSort

代码实现

上面的Arrays.copyOfRange 确实这段代码的一个性能瓶颈。每次递归调用都创建新数组，会带来大量的内存分配和数据拷贝开销。但是实际上我们只需要告诉排序方法：“请对 arr 数组中从 left 索引到 right 索引的这部分进行排序”。这样，所有的操作都在同一个原始数组上进行，完全避免了创建中间数组。

为了实现这一点，我们需要引入一个辅助数组（通常称为 temp），用于在合并（merge）阶段暂存数据。这个 temp 数组只需在整个排序过程开始时创建一次，然后反复复用。

下面是优化后的代码实现：

算法分析

  • 稳定性：稳定

  • 时间复杂度：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)

  • 空间复杂度：O(n)