#include <iostream>#include <algorithm>#include <vector>using namespace std;/* *歸并排序 *思想：將待排數組多次二分為單個數（遞歸），再回溯合并為有序序列 *步驟1：遞歸二分待排數組 *步驟2：將二分數組合并為有序序列，放在零時數組中 *步驟3：將零時序列賦值給待排序序列 *步驟4：回溯 *//* * 合并方法 * 待排序序列，開始索引，結束索引 */void Merge(vector<int>&a, int s, int e, vector<int>&temp){ int mid = (s + e) / 2; int i = s, j = mid + 1; int k = s; while (i<=mid&&j<=e) { if (a[i]<=a[j]) temp[k++]=a[i++]; else temp[k++]=a[j++]; } //只需要管前面的是否還剩余 while (i <= mid) temp[k++]=a[i++]; for (i = s; i < k;i++) a[i] = temp[i];}/* * 遞歸二分 */void MergeSort(vector<int>&a, int s, int e, vector<int>&temp){ if (s<e) { int mid = (s + e) / 2; MergeSort(a, s, mid, temp); MergeSort(a, mid + 1, e, temp); Merge(a, s, e,temp); }}int main(){ int n; while (cin>>n) { vector<int>a(n); vector<int>temp(n);//傳遞零時容器進去，不用每次合并時都創建一個新的零時容器，節約時間 for (int i = 0; i < n; i++) cin >> a[i]; MergeSort(a, 0, n - 1, temp); for (int t : a) { cout << t << ' '; }; } return 0;}
