Divide(分割):將陣列對半分成兩個子陣列 Conquer(解決):遞迴排序子陣列 Combine(合併):將兩個已排序的子陣列合併 時間複雜度:T(n) = 2T(n/2) + O(n) = O(n log n) 空間複雜度:O(n)(需要額外空間存放合併結果) 穩定性:穩定排序(相等元素保持原順序)
T(n) = 2T(n/2) + O(n) = O(n log n)
O(n)