归并排序概述

归并排序是一种基于分治策略的经典排序算法，通过递归地将数组拆分为更小的子数组，排序后再合并，最终实现整体有序。其时间复杂度为 ，适用于大规模数据排序。

算法原理

归并排序的核心思想是“分而治之”：

1. 分：将待排序数组递归地分成两半，直到子数组长度为1（天然有序）。
2. 治：将两个已排序的子数组合并为一个有序数组，合并时通过双指针遍历比较元素。

关键步骤分析

递归拆分

• 计算中点 。
• 对左右子数组递归调用归并排序。

合并操作

• 创建临时数组存储合并结果。
• 比较左右子数组元素，按序放入临时数组。
• 处理剩余未合并的元素。

代码实现示例（C++）

#include<bits/stdc++.h>
using namespace std;  // 这个就不用说了吗
int a[500010],b[500010];    // 定义
void m_sort(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;    // 计算中间值
    m_sort(l,mid);        // 因为当一个数组只有一个输的时候，肯定是有顺序的
    // 所以要一直分一半
    m_sort(mid+1,r);    // 分为两个区间l~mid和mid+1~r
    int i=l,j=mid+1,k=l;    // 定义指针
    while(i<=mid&&j<=r){    // 判断条件
        if(a[i]<=a[j])b[k++]=a[i++];     // 如果a[i]更小，则保存a[i]
        else if(a[i]>a[j])b[k++]=a[j++]; // 如果a[j] 更小，则保存a[j]
    }
    while(i<=mid)b[k++]=a[i++];   // 还有剩余的，记得保存
    while(j<=r)b[k++]=a[j++];   // 还有剩余的，记得保存
    for(int i=l;i<=r;i++)a[i]=b[i];    // 最终要输出的是a[i]
}
int main(){
    int n;    
    cin>>n;   // 输入
    for(int i=1;i<=n;i++)cin>>a[i];
    m_sort(1,n);    // 排序
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";   // 输出
    return 0;
}

性能与优化

时间复杂度

• 最优、最坏和平均情况下均为 ，因拆分和合并的递归深度为 ，每层合并操作耗时 。

空间复杂度

• 需要额外  空间存储临时数组，是非原地排序算法。

优化方向

1. 对小规模子数组改用插入排序，减少递归开销。
2. 避免频繁内存分配，预分配全局临时数组。

应用场景

• 适合链表排序（无需随机访问）。
• 外部排序（如大数据文件的分块排序与合并）。
• 稳定性要求高的场景（归并排序是稳定排序）。

与其他排序算法对比

• 快速排序：平均  但最差 ，归并排序更稳定但空间占用更高。
• 堆排序：原地排序但不稳定，缓存局部性较差。

扩展变体

• 自底向上归并排序：迭代实现，避免递归栈开销。
• 多路归并排序：用于外部排序，合并多个有序块。