算法1

归并排序：从setp = 2 开始比较每一段元素是否有序

C++ 代码

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

const int MAX_N = 110;
int arrA[MAX_N], arrB[MAX_N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arrA[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> arrB[i];
    }
    int k = 2;
    while (k < n && arrB[k] >= arrB[k - 1]) k++;

    int j = k;
    while (j < n && arrA[j] == arrB[j]) j++;
    if (j == n) {
        printf("Insertion Sort\n");
        sort(arrB, arrB + k + 1);
    }
    else {
        printf("Merge Sort\n");
        int step = 1;
        bool flag = true;
        while (flag) {
            step *= 2;
            for (int i = 0; i < n; i += step) {
                int m = min(i + step, n);
                for (int j = i + 1; j < m; j++) {
                    if (arrB[j] < arrB[j - 1]) {
                        flag = false;
                        break;
                    }
                }
                //说明该段无序
                if (flag == false) {
                    sort(arrB + i, arrB + m);
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (i) printf(" ");
        printf("%d", arrB[i]);
    }
}