[Algo] 2.3 Designing algorithms

incremental approach: 像insertion sort這樣子的演算法，過程是A[1...j], A[1...j+1]，逐漸完成
divide-and-conquer approach: 把整個問題切成若干個小問題，然後對每個小問題一一擊破，最後再把這些答案整合起來變成原本問題的答案

Merge Sort
Rationale
整個演算法主要是根據divide-and-conquer的方式下去進行。假設A[p...r]是一個我們想要實行sorting的一個序列。先把A[p...r]分成兩個小一點的序列，叫做L: A[p...q]跟R: A[q+1...r]，假設我們有能力可以把L和R各自排序好，那把L和R組合起來變成A[p...r]就是一件簡單的事情了。

就好比現在有兩堆大小順序排好的牌堆，點數小的牌在上面，點數大的牌在下面。我們只要比較這兩個牌堆的最上面那張牌，比較小的就把他抽出來，直到某一個牌堆全部都被抽光。這樣就可以很簡單的把這兩副牌堆組合成一個排序好的牌堆。我們就是依據這個道理把L和R兩個序列合成為A[p...r]。

回到我們的前提，就是L和R必須得是排序好的序列。於是這個問題就變成是一個recursive的問題，要把A[p...r]排序好就得先把L和R排序好，排序L就跟排序A其實是同一個問題。所以這個演算法就是把A[p...r]切割成兩個序列A[p...q]和A[q+1...r]，A[p...q]和A[q+1...r]也是這樣一直分割下去，分割到最小的單位就是長度為1的序列了。

pseudocode
@{
\proc{Merge-Sort}(A, p, r)
\li \If p < r
\li \;\;\;\;q = \lfloor(p+r)/2\rfloor
\li \;\;\;\;\proc{Merge-Sort}(A, p, q)
\li \;\;\;\;\proc{Merge-Sort}(A, q+1, r)
\li \;\;\;\;\proc{Merge}(A, p, q, r)
}@


@{
\proc{Merge}(A, p, q, r)
\li n_1 = q - p + 1
\li n_2 = r - q
\li \textup{// create arrays}\;L[1..n_1 + 1]\;\textup{and}\;R[1..n_2 + 1]
\li \For i = 1\;\textbf{to}\;n_1
\li \;\;\;\;L[i] = A[p + i - 1]
\li \For j = 1\;\textbf{to}\;n_2
\li \;\;\;\;R[j] = A[q + j]
\li L[n_1 + 1] = \infty
\li R[n_2 + 1] = \infty
\li \For k = p \;\textbf{to}\;r
\li \;\;\;\;\If L[i] \leq R[j]
\li \;\;\;\;\;\;\;\;A[k] = L[i]
\li \;\;\;\;\;\;\;\;i = i + 1
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;A[k] = R[j]
\li \;\;\;\;\;\;\;\;j = j + 1
}@