MergeSort归并排序

归并排序的主要是采用的分治的思想，将一个区间不断的二分划分，然后做归并操作

代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;

void Merge(int* a,int l,int r,int* res){
    int len = (r-l)/2 + 1;
    int left = l;
    int right = l+len;
    int res_index = l;
    while(left<l+len && right<r+1){
        if(a[left] <= a[right]) res[res_index++] = a[left++];
        else                    res[res_index++] = a[right++];
    }
    while(left<l+len){ res[res_index++] = a[left++]; }
    while(right<r+1){  res[res_index++] = a[right++]; }
    return;
}

void MergeSort(int *a,int l,int r,int *res){
    if(l<r){
        int len = (r-l)/2;
        MergeSort(a,l,l+len,res);
        MergeSort(a,l+len+1,r,res);
        Merge(a,l,r,res);
        for(int i = l;i<=r;i++)
            a[i] = res[i];
    }
    return;
}

int a[MAXN],res[MAXN];

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i<n;i++)
        scanf("%d",&a[i]);
    MergeSort(a,0,n-1,res);
    for(int i = 0;i<n;i++)
        printf("%d ",a[i]);
    return 0;
}