归并排序模板

//归并排序 有空看一下 Timsort 
int a[1000] = {4,1,7,8,5,6,3,2,9};
int len = 1000;

void merge(int first,int last)
{
    int mid = (last+first)/2;
    int i = first,j = mid+1;
    int b[last-first+1],bi=0; //搬运
    while(i<=mid&&j<=last)
    {
        if(a[i]<=a[j]) b[bi++] = a[i++];
        else           b[bi++] = a[j++];
    }
    while(i<=mid&&!(j<=last)) b[bi++] = a[i++];
    while(!(i<=mid)&&j<=last) b[bi++] = a[j++];

    for(i=first,j=0;i<=last;i++,j++)
        a[i] = b[j];
}

void merge_sort(int first,int last)
{
    if(first>=last) return ;
    merge_sort(first,(last+first)/2);
    merge_sort((last+first)/2+1,last);
    merge(first,last);
}
int main()
{
    srand(time(NULL));
    for(int i=0;i<len;i++)
        a[i] = rand();

    merge_sort(0,len-1);

    for(int i:a)
        cout<<i<<endl;


    return 0;
}