归并排序

2——路归并排序，将序列两两分组进行排序，共有n/2组；然后再将这些组两两进行合并排序，得到n/4组，以此类推，直到只剩下一个组为止，此时这个组便是有序的。

两两分组的时候，可以用基于二分的思想进行分组。

void mergesort(int *a,int l,int r)
{
    if(l>=r)
        return;
    else
    {
        int mid=l+(r-l)/2;
        mergesort(a,l,mid);
        mergesort(a,mid+1,r);
        my_merge(a,l,mid,mid+1,r);
    }
}

归并排序
void my_merge(int *a,int l1,int r1,int l2,int r2)//两个有序序列，合并为一个有序序列，tow point ：将两个有序序列合并为一个有序序列，O(n)

void my_merge(int *a,int l1,int r1,int l2,int r2)//两个有序序列，合并为一个有序序列
{
    int temp[r2-l1+1],index=0,i=l1,j=l2;
    while(i<=r1&&j<=r2)
    {
        if(a[i]<a[j])
            temp[index++]=a[i++];
        else
            temp[index++]=a[j++];
    }

    while(i<=r1)
        temp[index++]=a[i++];
    while(j<=r2)
        temp[index++]=a[j++];
    for(i=0;i<index;++i)
        a[l1+i]=temp[i];
}

/**
    归并排序
    tow point ：将两个有序序列合并为一个有序序列，O(n)
*/
/**
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
void my_merge(int *a,int l1,int r1,int l2,int r2)//两个有序序列，合并为一个有序序列
{
    int temp[r2-l1+1],index=0,i=l1,j=l2;
    while(i<=r1&&j<=r2)
    {
        if(a[i]<a[j])
            temp[index++]=a[i++];
        else
            temp[index++]=a[j++];
    }
 
    while(i<=r1)
        temp[index++]=a[i++];
    while(j<=r2)
        temp[index++]=a[j++];
    for(i=0;i<index;++i)
        a[l1+i]=temp[i];
}
 
void mergesort(int *a,int l,int r)
{
    if(l>=r)
        return;
    else
    {
        int mid=l+(r-l)/2;
        mergesort(a,l,mid);
        mergesort(a,mid+1,r);
        my_merge(a,l,mid,mid+1,r);
    }
}
 
int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;++i)
        cin >> a[i];
    mergesort(a,0,n);
    for(auto b: a)
        cout << b << ' ';
    cout << endl;
 
    cout << "Hello world!" << endl;
    return 0;
}