分治思想：分→治→合
分治（Divide and Conquer）是一种解决问题的策略，就像整理一间乱房间：先把房间分成几个小区域（分），然后分别打扫每个区域（治），最后把干净的区域合并起来（合）。分治算法通常用递归实现，将大问题分解为多个相同类型的子问题，直到子问题足够简单，再合并子问题的解得到原问题的解。
归并排序流程
归并排序是分治思想的典型应用。流程如下：
- 分：将数组从中间分成两个子数组，递归地对它们排序。
- 治：当子数组长度为1时，它自然有序（递归终止条件）。
- 合：将两个有序子数组合并成一个有序数组。
就像把一副乱序的扑克牌不断对半切，直到每堆只剩一张牌，然后两两合并成有序堆。
合并两个有序数组（双指针）
合并两个有序数组时，使用双指针技术：两个指针分别指向两个数组的起始位置，比较指针所指元素，将较小的放入结果数组，并移动该指针。重复直到一个数组耗尽，再将另一个数组剩余元素全部放入。这个过程就像两列按身高排好的队伍，每次从队首选出较矮的人进入新队列。
为什么是 O(n log n)
| 阶段 | 复杂度 | 说明 |
|---|---|---|
| 分 | O(log n) | 每次将数组对半分割，深度为 log₂n。 |
| 合 | O(n) | 每层合并所有元素，总元素数为 n。 |
| 总 | O(n log n) | 每层 O(n)，共 log n 层，所以 O(n log n)。 |
归并排序的时间复杂度稳定为 O(n log n)，无论输入数据如何，因为分割和合并的步骤固定。
分治还能解什么（快排/求逆序对等）
分治思想还能解决许多问题：
- 快速排序：选一个基准，将数组分为小于和大于基准的两部分，递归排序。
- 求逆序对：利用归并排序过程，在合并时统计逆序对数量。
- 最大子数组和：将数组分成两半，最大子数组要么在左半、右半，要么跨越中点。
- 大整数乘法：将大数分成高位和低位，递归计算。
分治的核心是找到合适的分解方式，使子问题独立且容易合并。