课本上没有源码，但看起来思路不错，于是自己写了个

    void NaturalMergeSort(T a[], int n)
    {
        T *ta = new T [n];//临时数组
        int b[n];//包含各有序子序列断点
        int lenb=0;
        b[lenb++]=-1;//b[0]始终指首
        for (int i=0; i<n-1 ; i++ )//分断点
            if(a[i]>a[i+1]) b[lenb++]=i;
        b[lenb++]=n-1;//指尾

        while(lenb>2)//不断合并
        {
            int i=0,newlenb=1;
            for (i=0; i<lenb-2; i+=2)
            {
                Merge(a, ta, b[i]+1, b[i+1], b[i+2]);//相邻的两个两个合并
                for (int j=b[i]; j<=b[i+2]; j++ )//拷回
                    a[j]=ta[j];
                b[newlenb++]=b[i+2];//b一定越来越小，所以可以重复利用
            }

            if(i==lenb-2) b[newlenb++]=b[lenb-1];//处理最后的孤点
            lenb=newlenb;
        }
    }

    void Merge(T c[], T d[], int l, int m, int r)
    {
        // Merge c[l:m]] and c[m:r] to d[l:r].
        int i = l,    // cursor for first segment
                j = m+1,  // cursor for second
                    k = l;    // cursor for result

        // merge until i or j exits its segment
        while ((i <= m) && (j <= r))
            if (c[i] <= c[j]) d[k++] = c[i++];
            else d[k++] = c[j++];

        // take care of left overs
        if (i > m) for (int q = j; q <= r; q++)
                d[k++] = c[q];
        else for (int q = i; q <= m; q++)
                d[k++] = c[q];
    }