时间复杂度

最坏时间复杂度	最好时间复杂度
O(nlogn)	O(nlogn)

归并排序并不依赖于数组的起始状态，所以最好，最坏时间复杂度都是一样的，并且归并排序时稳定的，而快速排序是不稳定的 归并排序时间复杂度分析

主要步骤

1. 归并排序是分治算法，第一步就是要划分区间
2. 递归的处理子问题
3. 合并子问题。由于在第二步会形成两个分别有序的子区间，所以这里使用双指针算法，并使用一个中间数组来进行子区间的合并

实现

题目以及讲解 在合并子问题的步骤中，第一个循环是将主体部分进行合并到中间数组中，然后看子区间有没有剩下的，再补充进去，然后是覆盖原数组，注意i要从l开始到r停止，因为当前处理的是m数组的一个从l到r的子区间

归并排序的证明与边界分析

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;

int m[N],tmp[N];



void merge_sort(int m[],int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    
    merge_sort(m,l,mid);
    merge_sort(m,mid+1,r);
    
    int i=l,j=r-1,k=0;
    while(i<=mid&&j<=r)
    {
        if(m[i]<=m[j]) tmp[k++]=m[i++];
        else tmp[k++]=m[j++];
    }
    while(i<=mid) tmp[k++]=m[i++];
    while(j<=r) tmp[k++]=m[j++];
    
    for(int i=l,j=0;i<=r;i++,j++) m[i]=tmp[j];

}


int main()
{
    int n=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&m[i]);
    }
    
    merge_sort(m,0,n-1);
    
    for(int i=0;i<n;i++)
    {
        printf("%d ",m[i]);
    }
    
    return 0;
}