對於 n 筆資料，取其中一半 n/2 筆用插入排序法排序，時間複雜度為 O((n/2)^2) = O(n^2/4) = O(n^2)。
另一半 n/2 筆用快速排序法排序，最糟情況下快速排序的時間複雜度為 O(n^2)。因為快速排序是選擇一個元素作為基準值，將小於基準值的元素放到左邊，大於基準值的元素放到右邊，如果每次基準值都選到了最大或最小的元素，那麼每次切割區間都只能減少一個元素，因此需要進行 n 次切割，時間複雜度為 O(n^2)。
接著用合併排序法將兩列排序好的資料做最後的排序，最糟情況下合併排序的時間複雜度為 O(n log n)。因為合併排序是不斷將數列切割成兩半，直到每個小段都只剩下一個元素，再將小段兩兩合併，重複進行合併直到排序完成。因此需要進行 log n 輪切割和合併，每輪需要對 n 個元素進行比較，時間複雜度為 O(n log n)。
因此，整個排序工作在最糟情況下的最後總時間複雜度為 O(n^2) + O(n^2) + O(n log n) = O(n^2)。
阿摩線上測驗
登入