Insert or Merge

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print in the first line either “Insertion Sort” or “Merge Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
1
2
3

Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0
1
2

Sample Input 2:

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
1
2
3

Sample Output 2:

Merge Sort
1 2 3 8 4 5 7 9 0 6
1
2

题目大意：
给你长度为n的两个序列，判断第二个序列是由第一个序列经过插入排序还是归并排序得来的结果，输出使用哪种排序方法，以及输出第二个序列下一趟排序的序列。

解题思路：
一开始我想用递归的方式来写归并排序，写完之后发现这个题不能用递归的方法写归并排序，否则得不到目标序列。最后改用非递归的方式写归并排序则顺利AC。当然这个题其实也可以不写递归排序，直接用sort模拟归并排序的非递归排序过程也可以。

解法一：

#include
using namespace std;
const int maxn = 110;
int merg[maxn], insert[maxn], b[maxn], n;
bool judge(int a[]) {
    for(int i = 0; i < n; i++) {
        if(a[i] != b[i]) return false;
    }
    return true;
}
bool InsertSort(int a[]) {
    for(int i = 1; i < n; i++) {
        if(a[i] < a[i-1]) {
            int temp = a[i], j;
            for(j = i - 1; temp < a[j]; j--) a[j+1] = a[j];
            a[j+1] = temp; 
        }
        if(judge(a)) {
            puts("Insertion Sort");
            int temp = a[++i], j;
            for(j = i - 1; temp < a[j]; j--) a[j+1] = a[j];
            a[j+1] = temp;
            printf("%d", a[0]);
            for(int i = 1; i < n; i++) printf(" %d", a[i]);
            return true;
        }
    }
    return false;
}
int temp[maxn] = {0};
void merge(int a[], int low, int mid, int high) {
    for(int i = 0; i < n; i++) temp[i] = merg[i];
    int i, j, k;
    for(i = k = low, j = mid+1; i <= mid && j <= high; k++) {
        if(temp[i] <= temp[j]) a[k] = temp[i++];
        else a[k] = temp[j++];
    }
    while(i <= mid) a[k++] = temp[i++];
    while(j <= high) a[k++] = temp[j++];
}
void MergeSort(int a[]) {
	//step为组内元素个数，step / 2为左子区间元素个数
    for(int step = 2; step / 2 < n; step *= 2) {
        for(int i = 0; i < n; i += step) {
            int mid = i + step / 2 - 1;//每step个元素一组，组内[i, min(i+step, n+1)] 进行排序
            if(mid + 1 <= n - 1) { //如果有右子区间则归并
                merge(a, i, mid, min(i + step - 1, n - 1));
                //左子区间为[i, mid],右子区间为[mid+1, min(i+step-1, n)]
            }
        }
        if(judge(a)) {
            puts("Merge Sort");
            step *= 2;
            for(int i = 0; i < n; i += step) {
                int mid = i + step / 2 - 1;
                if(mid + 1 <= n - 1) {
                    merge(a, i, mid, min(i + step - 1, n - 1));
                }
            }
            printf("%d", merg[0]);
            for(int i = 1; i < n; i++) printf(" %d", merg[i]);
            return;
        }
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &insert[i]);
        merg[i] = insert[i];
    }
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    if(InsertSort(insert)) return 0;
    MergeSort(merg);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

解法二：
用sort模拟

#include
using namespace std;
const int maxn = 110;
int merg[maxn], insert[maxn], b[maxn], n;
bool judge(int a[]) {
    for(int i = 0; i < n; i++) {
        if(a[i] != b[i]) return false;
    }
    return true;
}
bool InsertSort(int a[]) {
    for(int i = 1; i < n; i++) {
        if(a[i] < a[i-1]) {
            int temp = a[i], j;
            for(j = i - 1; temp < a[j]; j--) a[j+1] = a[j];
            a[j+1] = temp; 
        }
        if(judge(a)) {
            puts("Insertion Sort");
            int temp = a[++i], j;
            for(j = i - 1; temp < a[j]; j--) a[j+1] = a[j];
            a[j+1] = temp;
            printf("%d", a[0]);
            for(int i = 1; i < n; i++) printf(" %d", a[i]);
            return true;
        }
    }
    return false;
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &insert[i]);
        merg[i] = insert[i];
    }
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    if(InsertSort(insert)) return 0;
    puts("Merge Sort");
    bool flag = false;
    int len = 2;
    while(!flag) {
        if(judge(merg)) flag = true;
        for(int i = 0; i < n; i+=len) {
            sort(merg + i, merg + min(i + len, n));
        }
        len *=2;
    }
    printf("%d", merg[0]);
    for(int i = 1; i < n; i++) printf(" %d", merg[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51