2.1.6 Merge Sort v.s. Quick Sort

• 兩者其實非常相似, 都是把資料分成兩邊, 直到不能再分了, 才把資料合起來. 不過quick sort最大的特色就是會有partition的這個動作, 講白了就是把數字分好大小後再繼續往下分, 所以這樣循環下去分到最小後, 也表示完成了排序的動作了.

• 在大部分的worst case下, merge sort是優於quick sort的, 再加上merge sort的worst case跟quick sort的best case之時間複雜度是一樣的, 這樣看來似乎是merge sort比較快(理論上).

• 可是實際上來說, 如果兩者都用遞迴的方式去實作的話, quick sort的method call為N, 那merge sort就會是2N-1(註1), 即merge sort多花了一倍的method call. 如果用迴圈來做, merge sort會花比較多時間在記憶體上面, 因為它不是in-place sorting.

• 不過merge sort有一個很好的特性: 它是穩定的(stable sorting), 穩定的意思是說, 排序前與排序後, 擁有相同key值的兩個資料, 彼此之間的順序是一樣的.

• 最後, 這兩者都是Divide and Conquer的做法, 只是quick sort為先苦後樂(遞迴之前的partition比較麻煩, 遞迴完後就沒事了); 而merge sort是先樂後苦(進入遞迴之前都沒事, 但是遞迴之後的合併動作就累了).

註1: 參閱原始碼, 注意merge function的step1~step2, 這是第一次的N, 即排序當前分割後的結果, 而step3, 把排序好的結果放回原本的array, 也會有一次N.