【归并排序的基本思想】归并排序（Merge Sort）是一种经典的排序算法，属于分治法（Divide and Conquer）的典型应用。其基本思想是将一个大问题分解为若干个小问题分别解决，然后将结果合并，从而得到最终的解决方案。
归并排序的核心步骤可以概括为三步：
1. 分割（Divide）：将待排序的数组一分为二，分成两个子数组。
2. 递归排序（Conquer）：对每个子数组进行递归排序，直到子数组长度为1或0时停止。
3. 合并（Combine）：将两个已排序的子数组合并成一个有序的数组。
通过这种方式，归并排序能够高效地完成排序任务，尤其适用于大规模数据的排序。
归并排序基本思想总结
| 步骤 | 描述 | 特点 |
| 分割 | 将数组不断对半拆分，直到每个子数组只有一个元素 | 递归操作，时间复杂度为 O(log n) |
| 排序 | 对每个子数组进行排序，因为单个元素已视为有序 | 递归终止条件 |
| 合并 | 将两个有序的子数组合并为一个更大的有序数组 | 关键步骤，时间复杂度为 O(n) |
归并排序的特点
- 稳定性：归并排序是一种稳定的排序算法，不会改变相同元素之间的相对顺序。
- 时间复杂度：无论数据是否有序，时间复杂度均为 O(n log n)，效率较高。
- 空间复杂度：需要额外的存储空间用于合并过程，空间复杂度为 O(n)。
- 适用性：适合处理大规模数据，尤其在外部排序中表现优异。
示例说明
假设有一个无序数组：`[5, 2, 8, 6, 1]`
1. 分割为 `[5, 2]` 和 `[8, 6, 1]`
2. 继续分割，直到每个子数组只有一个元素：
- `[5]`, `[2]`, `[8]`, `[6]`, `[1]`
3. 合并 `[5]` 和 `[2]` 得到 `[2, 5]`
4. 合并 `[8]` 和 `[6]` 得到 `[6, 8]`
5. 合并 `[6, 8]` 和 `[1]` 得到 `[1, 6, 8]`
6. 最终合并 `[2, 5]` 和 `[1, 6, 8]` 得到完整有序数组 `[1, 2, 5, 6, 8]`
归并排序以其稳定性和高效的性能，在实际应用中被广泛使用，尤其是在需要处理大量数据时。尽管它需要额外的空间，但在现代计算机系统中，这种代价通常是可接受的。