Merge sort

2—— Path merging and sorting , Sort the sequence in pairs , share n/2 Group ; Then merge and sort these groups in pairs , obtain n/4 Group , And so on , Until there is only one group left , At this point, the group is orderly .

In pairs , You can use the idea of dichotomy to group .

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);
    }
}

Merge sort
void my_merge(int *a,int l1,int r1,int l2,int r2)// Two ordered sequences , Merge into an ordered sequence ,tow point ： Combine two ordered sequences into one ,O(n)

void my_merge(int *a,int l1,int r1,int l2,int r2)// Two ordered sequences , Merge into an ordered sequence
{
    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];
}

/**
     Merge sort 
    tow point ： Combine two ordered sequences into one ,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)// Two ordered sequences , Merge into an ordered sequence 
{
    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;
}