C++ PTA 1035 插入与归并 (25 分)

https://pintia.cn/problem-sets/994805260223102976/problems/994805286714327040

• equal(a,a+i,b)
• 比较a，b两容器中长度为 i 的数据是否相等，返回bool值。包含在algorithm中

若是插入排序，必定存在某个位置，在这个位置前，排序数组是有序的；位置后，原数组和排序后数组相等。

否则就是归并排序。直接模拟归并排序的流程，判断在哪一步排序数组等于模拟归并数组，之后再进行一次归并即可。

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int n,a[100], b[100], insertPos;
    bool isInsert = true;
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i];
    for(int i=0;i<n;i++)
        cin >> b[i];
    for(insertPos=1; insertPos<n; insertPos++)
        if(b[insertPos]<b[insertPos-1])
            break;
    for(int i=insertPos; i<n; i++)
        if(a[i] != b[i])
        {
            isInsert = false;
            break;
        }
    if(isInsert)
    {
        cout << "Insertion Sort" << endl;
        sort(a,a+insertPos+1);
    }
    else
    {
        cout << "Merge Sort" << endl;
        int temp = 2;
        while(!equal(a,a+n,b))
        {
            for(int i=0; i<n; i+=temp)
                sort(a+i,a+min(i+temp, n));
            temp = temp*2;
        }
        for(int i=0; i<n; i+=temp)
                sort(a+i,a+min(i+temp, n));
    }
    for(int i=0; i<n-1; i++)
        cout << a[i] << ' ';
    cout << a[n-1];
    return 0;
}