思路
考察经典的排序算法
判断merge的下一轮 没有一个很好的特征作为条件，直接去模拟的思路非常妙！
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
int ori[maxn], aft[maxn];
int main() {
int n;
cin>>n;
for (int i = 0; i < n; i++) {
cin>>ori[i];
}
for (int i = 0; i < n; i++) {
cin>>aft[i];
}
int q = 1;
while (aft[q] >= aft[q - 1] && q < n) q++;
int k = q;
while (ori[q] == aft[q] && q < n) q++;
if (q == n) {
cout<<"Insertion Sort"<<endl;
if (k == n) k--;
sort(aft, aft + k + 1);
for (int i = 0; i < n; i++) {
cout<<aft[i];
if (i != n - 1) cout<<" ";
else cout<<endl;
}
} else {
cout<<"Merge Sort"<<endl;
k = 1;
int flag = 0;
while (1) {
for (int i = 0; i < n; i += (k * 2)) {
int t = min(i + 2 * k, n);
sort(ori + i, ori + t);
}
if (flag == 1) break;
int j;
if (flag == 0) {
for (j = 0; j < n; j++) {
if (ori[j] != aft[j]) break;
}
if (j == n) flag = 1;
}
k *= 2;
}
for (int i = 0; i < n; i++) {
cout<<ori[i];
if (i != n - 1) cout<<" ";
else cout<<endl;
}
}
}
