void Merge(int *a, int ileft, int imid, int iright) //辅助函数

{

    int n1 = imid - ileft + 1; 

    int n2 = iright - imid; 

    int *Larray = new int[n1];

    int *Rarray = new int[n2];

    //分解

    for(int i = 0; i <= n1 - 1; i++)

    {

        Larray[i] = a[ileft+i];

    }

    for(int j = 0; j <= n2 - 1; j++)

    {

        Rarray[j] = a[imid+1+j];

    }

    //合并

    int i = 0, j =0;

    for(int k = ileft; k <= iright; k++)

    {

        if(i==n1) //Larray中已无元素(i越界)

        {

            a[k] = Rarray[j];

            j++;

        }

        else if(j==n2) //Rarray中已无元素(j越界)

        {

            a[k] = Larray[i];

            i++;

        }

        else

        {

            if(Larray[i]<=Rarray[j])

            {

                a[k] = Larray[i];

                i++;

            }

            else

            {

                a[k] = Rarray[j];

                j++;

            }

        }

    }

    delete []Larray;

    delete []Rarray;

}

void MergeSort(int *a, int ileft, int iright)  //接口

{

    if(ileft < iright)

    {

        int imid = (ileft + iright) / 2;

        MergeSort(a, ileft, imid);

        MergeSort(a, imid+1, iright);

        Merge(a, ileft, imid, iright);

    }

}