归并排序是一种基于**分治法**的高效排序算法，其核心思想是将数组不断拆分为更小的子数组，排序后再合并为有序的整体。以下是详细解释：
---
### **1. 算法步骤**
1. **分解**：
将数组递归地分成两半，直到每个子数组仅含有一个元素（此时视为已排序）。
2. **合并**：
将两个有序的子数组合并为一个有序数组。合并时，通过比较两子数组的元素，按顺序插入新数组，直至所有元素合并完成。
---
### **2. 合并过程详解**
- **双指针法**：
初始化两个指针分别指向两个子数组的起始位置，比较指针所指元素，将较小的元素放入结果数组，并移动指针。重复此过程，直到某一子数组遍历完毕。
- **处理剩余元素**：
将未遍历完的子数组的剩余元素直接追加到结果数组中。
**示例**：合并 `[1, 3]` 和 `[2, 4]`
1. 比较 `1` 和 `2`，取 `1`；
2. 比较 `3` 和 `2`，取 `2`；
3. 比较 `3` 和 `4`，取 `3`；
4. 剩余 `4` 放入结果；
最终结果：`[1, 2, 3, 4]`。
---
### **3. 时间复杂度与空间复杂度**
- **时间复杂度**：
- 每次分解为对数级（\(O(\log n)\)），每层合并需线性时间（\(O(n)\)）。
- 总时间复杂度为 \(O(n \log n)\)，无论数据是否有序，性能稳定。
- **空间复杂度**：
- 需额外 \(O(n)\) 空间存储临时数组，合并后释放。
---
### **4. 稳定性与适用场景**
- **稳定性**：
合并时若遇到相等元素，优先选取左子数组的元素，保持原有顺序，因此是**稳定排序**。
- **适用场景**：
- 需稳定排序或保证 \(O(n \log n)\) 时间的情况。
- 尤其适合链表排序，合并时仅需调整指针，空间复杂度可优化至 \(O(1)\)（迭代法）。
---
### **5. 优缺点对比**
- **优点**：
- 时间复杂度稳定为 \(O(n \log n)\)。
- 稳定，适合复杂对象排序。
- **缺点**：
- 需额外内存空间，不适合内存受限的场景。
---
### **6. 代码示例（Python）**
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
```
---
### **7. 优化与变体**
- **自底向上迭代法**：避免递归栈开销，适合空间敏感场景。
- **混合策略**：小数组使用插入排序减少递归深度（如TimSort）。
归并排序凭借其稳定性和可靠性能，成为许多编程语言标准库的排序基础（如Java、Python）。
