归并排序
归并排序是一种高效的排序算法，采用分治策略。它将数组递归地分成两半，分别排序后，再将两个有序的子数组合并成一个有序的数组。
算法原理
归并排序的基本思想是：将数组分成两半，递归地对每一半进行排序，然后将两个有序的子数组合并成一个有序数组。这个过程重复进行，直到子数组的大小为1（单个元素已经有序），然后开始合并。
算法步骤
- 如果数组长度为1或0，直接返回（已经有序）
- 将数组分成两半
- 递归地对左半部分进行归并排序
- 递归地对右半部分进行归并排序
- 将两个有序的子数组合并成一个有序数组
时间复杂度
- 最坏情况：O(n log n)
- 平均情况：O(n log n)
- 最好情况：O(n log n)
空间复杂度
O(n) - 归并排序需要额外的空间来存储临时数组，空间复杂度为 O(n)。
稳定性
归并排序是稳定的排序算法，相等元素的相对顺序不会改变。
适用场景
- 大规模数据的排序
- 需要稳定排序的场景
- 外部排序（数据量太大无法全部装入内存）
优缺点
- 优点：时间复杂度稳定为 O(n log n)；稳定排序；适合外部排序
- 缺点：需要额外的空间 O(n)；不是原地排序