## 分治(超基礎part) --- 分治 -> 分而治之 --- 所以很明顯 有兩part要實作 1.分 2.合 --- 最基礎運用 `merge sort` ---- 這個排序法應該很多人聽過了，就不多做介紹了 為什麼不用sort? 因為你正在學merge sort --- 完整程式碼 ---- 分：遞迴處理 每次都把前半及後半丟入函數 函數會自動回傳一個排好的vector 在底下實作合的部分就可以自動解決了 ---- ```cpp 1 vector<int> mergesort(vector<int> arr) { 2 3 int n = (int)arr.size(); 4 5 // 邊 界 條 件： 陣 列 長 度 等 於 1 6 if (n == 1) return arr; 7 8 // 遞 迴 排 序 左 半 邊 跟 右 半 邊 9 int mid = n/2; 10 vector<int> left, right; 11 for (int i = 0; i < n; i++) { 12 if (i < mid) left.push_back(arr[i]); 13 else right.push_back(arr[i]); 14 } 15 left = mergesort(left); 16 right = mergesort(right); 17 18 // 合 併 左 右 兩 半 邊 19 vector<int> sorted; 20 int Lptr = 0, Rptr = 0; 21 22 while (Lptr < (int)left.size() && 23 Rptr < (int)right.size()) { 24 25 if (left[Lptr] < right[Rptr]) { 26 sorted.push_back(left[Lptr]); 27 Lptr++; 28 29 } else { 30 sorted.push_back(right[Rptr]); 31 Rptr++; 32 33 } 34 35 } 36 37 while (Lptr < (int)left.size()) { 38 sorted.push_back(left[Lptr]); 39 Lptr++; 40 } 41 42 while (Rptr < (int)right.size()) { 43 sorted.push_back(right[Rptr]); 44 Rptr++; 45 } 46 47 return sorted; 48 49 } ``` ~~這是抄的，我懶得自己打~~ --- 額外思考：快速冪如何實作? 比merge sort簡單100倍，大約10~15行而已 hint 若b為偶數 $a^b = a^{\frac{b}{2}} * a^{\frac{b}{2}}$ hint 若b為奇數 $a^b = a^{\frac{b}{2}} * a^{\frac{b}{2}} * a$ ||c++會自動取整||