Sorting Problem
Input: A sequence of n numbers { \(a_0, a_1, ... , a_{n-1} \)}
Output: A permutation (reordering) { \(a'_0, a'_1, ... , a'_{n-1} \)} of the input sequence such that \( a'_0 \leq a'_1 \leq ... \leq a'_{n-1} \)
Merge Sort 概念
採用 divide-and-conquer approach:
Divide: 把長度為 \( n \) 的 array 分成兩半，左半邊 array: { \( a_0, a_1, ..., a_{\frac{n}{2}} \) } 右半邊 array: { \( a_{\frac{n}{2}+1}, a_{\frac{n}{2}+2}, ... , a_{n-1} \)}。
Conquer: 把左半邊 array 及右半邊 array 分別以 Merge Sort 進行 sorting。 (recursive)
Combine: merge 左半邊及右半邊 sorted array。
C++ implementation
範例
藍色數字為執行的順序。
Performance Analysis
Running time \(T(n) = 2 T(\frac{n}{2}) + O(n) \)
Worst case performance: \( O(n \log n) \)
Average case performance: \( O(n \log n) \)
Best case performance: \( O(n \log n) \)
Space complexity: \( O(n) \)
延伸閱讀
[書籍] Introduction to Algorithms, 3rd. edition - Chap 2
[WiKi] 合併排序
[WiKi] Merge sort
系列文章
Insertion Sort (插入排序)
Merge Sort (合併排序)
Heapsort (堆積排序)
