归并排序思路
归并排序是一种经典的分治算法，其基本思路可以简述为以下几步：
-
分解：将待排序的数组递归地分解成较小的子数组，直到每个子数组只包含一个元素为止。这里采用分治的思想，将问题不断地划分为规模更小的子问题。
-
合并：将相邻的子数组进行合并，得到较大的有序子数组。在合并的过程中，将两个有序子数组合并成一个更大的有序数组。这里利用了归并操作的特性，将两个有序数组合并成一个有序数组的操作。
-
递归：递归地应用上述步骤，直到所有的子数组都被合并成一个完整的有序数组为止。
具体步骤如下：
-
分解：将待排序的数组分成两个大致相等的子数组，直到每个子数组中只有一个元素为止。
-
合并：递归地将相邻的子数组合并成一个有序数组。合并过程中，比较两个子数组的首个元素，将较小的元素放入临时数组中，并移动相应的指针，直到其中一个子数组为空。
-
复制剩余元素：将剩余的元素复制到临时数组中。
-
替换原数组：将临时数组中的有序元素复制回原数组中相应的位置。
这样，当递归回到最初的调用时，原数组就会变成一个有序数组。
归并排序的时间复杂度为 O(n log n)，其中 n 是待排序数组的长度。由于归并排序是稳定的排序算法，因此在实际应用中广泛使用。