1 #include <fstream>  2 #include <iostream>  3 #include <vector>  4 #include <algorithm>  5   6 using namespace std;  7   8 //#define OJ  9  10 #ifdef OJ 11 #define fin cin 12 #else 13 ifstream fin("in.txt"); 14 #endif 15  16 vector<int> merge_vec; 17 vector<int> insert_vec; 18 vector<int> target; 19 vector<int> input; 20 int n; 21  22 #define MAX 0x70000000 23  24 int merge_sublist; 25 int merge_num; 26 int insert_i; 27  28 bool merge_sort(){ 29     int sublist = n; 30     int num = 1; 31     bool found = false; 32  33     while (sublist != 1){ 34         int list_cnt = 0; 35         for (int i = 0; i < sublist; i += 2){ 36             list_cnt++; 37             vector<int> s1, s2; 38             int s1_start = i * num; 39             int s1_end = s1_start + num > n ? n : s1_start + num; 40             int s2_start = s1_end; 41             int s2_end = s2_start + num > n ? n : s2_start + num; 42             int idx = i * num; 43  44             int cnt = 0; 45             while (idx < n && cnt++ < num){ 46                 s1.push_back(merge_vec[idx]); 47                 idx++; 48             } 49             cnt = 0; 50             while (idx < n && cnt++ < num){ 51                 s2.push_back(merge_vec[idx]); 52                 idx++; 53             } 54  55             vector<int> tmp; 56             int p1 = s1_start, p2 = s2_start; 57             while (p1 != s1_end || p2 != s2_end){ 58                 int v1 = p1 == s1_end ? 0x70000000 : merge_vec[p1]; 59                 int v2 = p2 == s2_end ? 0x70000000 : merge_vec[p2]; 60  61                 if (v1 < v2){ 62                     tmp.push_back(v1); 63                     p1++; 64                 } 65                 else { 66                     tmp.push_back(v2); 67                     p2++; 68                 } 69             } 70  71             for (int i = s1_start; i < s2_end; i++) 72                 merge_vec[i] = tmp[i - s1_start]; 73         } 74         sublist = list_cnt; 75         num *= 2; 76         bool flag = true; 77         for (int i = 0; i < n; i++){ 78             if (target[i] != merge_vec[i]){ 79                 flag = false; 80                 break; 81             } 82         } 83         if (flag){ 84             found = true; 85             merge_sublist = sublist; 86             merge_num = num; 87         } 88         if (found && !flag){ 89             return true; 90         } 91     } 92     return false; 93 } 94  95 bool insert_sort(){ 96     bool found = false; 97     for (int i = 0; i < n; i++){ 98         int j = 0; 99         for (; j < i; j++){100             if (insert_vec[j] > insert_vec[i])101                 break;102         }103         int swap_num = insert_vec[i];104         for (int k = i; k > j; k--){105             insert_vec[k] = insert_vec[k - 1];106         }107         insert_vec[j] = swap_num;108 109         bool flag = true;110         for (int i = 0; i < n; i++){111             if (insert_vec[i] != target[i]){112                 flag = false;113                 break;114             }115         }116         if (flag){117             insert_i = i + 1;118             found = true;119         }120         if (found && !flag){121             return true;122         }123     }124 125     return false;126 }127 128 int main(){129     fin >> n;130 131     target.resize(n);132     input.resize(n);133 134     for (int i = 0; i < n; i++){135         fin >> input[i];136     }137     for (int i = 0; i < n; i++){138         fin >> target[i];139     }140 141     merge_vec = input;142     bool res = merge_sort();143 144     if (res){145         cout << "Merge Sort" << endl;146         cout << merge_vec[0];147         for (int i = 1; i < n; i++){148             cout << " " << merge_vec[i];149         }150         cout << endl;151         return 0;152     }153 154     insert_vec = input;155     res = insert_sort();156 157     if (res){158         cout << "Insertion Sort" << endl;159         cout << insert_vec[0];160         for (int i = 1; i < n; i++){161             cout << " " << insert_vec[i];162         }163         cout << endl;164         return 0;165     }166 167 168     return 0;169 }