题目链接

#include<bits/stdc++.h>
using namespace std;
int arr[105];
vector<int> org,che,tmp; 
int n,x;
bool insertsort(){
    int flag=0;
    for(int i=1;i<n;i++){
        if(i!=1 &&tmp == che){
            flag=1;
        }
        sort(tmp.begin(), tmp.begin()+i+1);
        if(flag) return 1;
    }
    return 0;
}
void mergesort(){
    int flag=0; 
    for(int step=3;step/2 <= n;step*=2){
        if(step!=3 && tmp == che){
            flag=1;
        }
        for(int i=0;i<n;i+=step){
            sort(tmp.begin()+i, tmp.begin()+min(i+step,n)); //排序的终止位置 
        }
        if(flag==1){
            for(int i=0;i<tmp.size();i++){
                cout<<tmp[i];
                if(i!=tmp.size()-1) cout<<" ";
                else cout<<endl;
            }
            return;
        }
    }
}
int main(){

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        org.push_back(x);
    }
    for(int i=0;i<n;i++){
        cin>>x;
        che.push_back(x);
    }
    tmp=org;
    if(insertsort()){
        cout<<"Insertion Sort"<<endl;
        for(int i=0;i<tmp.size();i++){
            cout<<tmp[i];
            if(i!=tmp.size()-1) cout<<" ";
            else cout<<endl;
        }
    }else{
        cout<<"Merge Sort"<<endl;
        tmp = org;
        mergesort();
    }
    return 0;
}