归并排序

定义

归并排序是一种基于分治思想的排序算法。它先把序列不断二分到单个元素，再两两合并成更长的有序序列，直到整体有序。

原理

合并是核心：用两个指针分别指向两个有序子序列的开头，每次取较小者放入结果数组，直到一方耗尽再接上剩余部分。合并需要额外的辅助数组。归并排序性能稳定，不受输入分布影响，且是稳定排序。其思想也可改为自底向上的迭代实现，并天然适合外部排序与并行化。

复杂度

• 时间复杂度（最好/平均/最坏）：O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定

应用场景

• 要求稳定且性能稳定的排序
• 链表排序（无需额外空间即可合并）
• 海量数据的外部排序
• 统计逆序对