設計演算法

我們可以選擇的演算法設計技術有很多種。插入排序使用了遞增逼近(incremental approach)的方法 : 在排序子陣列之後，將單個元素插入子陣列的適當位置，產生出完成排列的子陣列。

分治法(Divide-and-Conquer)

有許多演算法使用了遞迴的結構進行設計 : 為了解決一個問題，將問題拆分後經過多次遞迴解決問題的子問題，最終合併結果並解決問題。這種演算法就是分治法的想法。分治法在每一層的遞迴會有三個步驟:

• 分解(Divide) : 將原問題分解成許多個子問題，每一個子問題都是原問題規模較小的實例。
• 解決(Conquer) : 遞迴的方式去求解各子問題，當子問題的規模夠小時，則直接求解。
• 合併(Combine) : 將子問題的解合併成原問題的解。

合併排序法(merge sort)

合併排序法(merge sort)就是一種由分治法實現的演算法，直觀上也是符合分治法的三個步驟

• 分解(Divide) : 分解待排序長度為的陣列，變成長度為長度的兩個子陣列。
• 解決(Conquer) : 使用合併排序法遞迴的排序兩個子陣列。
• 合併(Combine) : 合併兩個已經排序的子陣列產生出已經完成排序的原陣列。

當子陣列的長度為1時，表示子陣列已經完成排序，並開始合併去完成排序每一個子陣列。

合併排序法關鍵的操作步驟為'合併'，將兩個以排序的子陣列合併。我們通過MERGE(A, p, q, r)來完成合併，A為陣列，為陣列的下標，滿足。在合併的過程中，我們假設子陣列和都已經完成排序。將這兩個子陣列合併形成新的一個已經完成排序，規模更大的子陣列，並替換掉目前的子陣列。

合併的過程大約需要Θ的時間，其中是整個待排序陣列的元素個數。整個合併大概會執行以下操作。想像桌上有兩堆牌面朝上的撲克牌，每一堆都已經完成排序，最小的牌在每一堆的最上面。我們希望把這兩堆牌合併成單一已經排好序的撲克牌堆，並且完成之後牌面向下放在桌上。

來源

我們的操作為在牌面朝上的兩堆牌上選取最上面那一張，在這兩張牌中選出最小的那一張牌，把這張牌從剛剛的撲克牌堆移除，將這張牌牌面向下放置在桌上另外的位置，成為新的撲克牌堆，我們稱這一個堆為輸出堆。不斷重複這個步驟，直到有一堆撲克牌堆沒有撲克牌為止，這時候，我們只要拿起剩下一開始的撲克牌堆並將牌面向下放置到輸出堆。因為每一次我們只比較兩個撲克牌堆最上面的那張牌，計算每一個步驟都需要常數時間。最多執行n個步驟，因此合併需要Θ的時間。

下面的虛擬碼呈現了合併的作法，但我們加了一張額外的牌，這張牌的功用是避免每一個比較步驟都要檢查撲克牌堆是否為空的，這張牌我們稱為哨兵牌(Sentinel value)，或是信號牌(signal value)，它包含一個特殊的數值，可以幫助我們簡化程式碼，我們設這個值為∞，這張牌必定會在每一個撲克牌堆的最下方(因為沒有數值比他大)，當我們看到某一堆露出哨兵牌，表示這個撲克牌堆為空，如果發生兩個堆都露出哨兵牌，則我們可以知道所有非哨兵牌都已經放入輸出堆。

MERGE(A, p, q, r)
A表示輸入的牌組，p表示L的起始index(A的起始index)，q為R的起始index(A的中間index)，r表示A的尾index。

n1 = q - p + 1
n2 = r - q
let L[1...n1 + 1] and R[1...n2 + 1] be new arrays
for i = 1 to n1
    L[i] = A[p + i - 1]
for j = 1 to n2
    R[j] = A[q + j]
L[n1 + 1] = ∞
R[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
    if L[i] <= R[j]
        A[k] = L[i]
        i = i + 1
    else A[k] = R[j]
        j = j + 1

第10行以前表示將A陣列猜分成兩個部分，左子陣列和右子陣列，第12行迴圈，k從給定的A陣列起始index p開始，一路走訪到結束index r，i和j表示左子陣列的index和右子陣列的index，如圖(a)表示。

進入迴圈迭代，比較和，發現，因此將R[0]放入A陣列中，並將R的index j往後走一格，表示1已經放入A陣列中，A陣列的index k也往後走一格，如圖(b)所示。

不斷進入迭代，進行比較後放入A陣列中，如果其中一個子陣列碰到無限大，則表示該陣列所有元素已經放入A陣列中。

整個MERGE具體的執行過程如下:

• 第1行表示子陣列的長度。
• 第2行表示子陣列的長度。
• 第3行宣告長度分別為和的陣列L和R，每個陣列保留多1的長度是為了放入哨兵牌。
• 第4行到第5行的for迴圈將子陣列複製到。
• 第6行到第7行的for迴圈將子陣列複製到。
• 第8行到第9行將哨兵放入陣列L和R的末端
• 第10行到第17行經過循環不變式，執行個基本步驟:
• • 在開始第12行到第17行for迴圈的每一次迭代，子陣列按照從小到大排序，包含和中個最小元素，得出和是各自在陣列中還沒被複製回A陣列的最小元素。

我們需要證明第12行到第17行for迴圈的第一次迭代之前循環不變式成立，每一次迭代之前也成立，最後一次迭代結束後也成立。這個循環不變式提供某些性質幫助我們證明正確性。

• 初始化 : 在第一次迭代之前，for的初始條件，所以為空。這個空的子陣列裡面包含L和R的個最小元素，又因為，所以和都是各自所在的陣列中未被複製到A陣列的最小元素。

• 保持 : 我們假設。這時候，是沒有放回A陣列的最小元素，子陣列包含個最小元素。在for中增加k值和i值，為了下次迭代重新建立了該循環不變式。若，則第16到17行執行適當的操作來維持循環不變式。

• 終止 : 終止時。根據循環不變式，子陣列就是由小到大排序，且包含和中個最小元素。陣列L和R一起包含個元素。除兩個哨兵元素外，其他元素都已經放入A陣列中。

我們已知，第1到3行和第8到11行每一行都需要常數時間，第4到7行的for迴圈需要ΘΘ的時間，第12行到17行的for迴圈有n次迭代，每一次迭代也需要常數時間。

MERGE-SORT的主要想法，就是將兩個子陣列MERGE-SORT之後，在MERGE起來，會將猜分成兩個子陣列和，前者和後者均有個元素。

MERGE-SORT(A, p, r)

if p < r
    q = (p + r) / 2
    MERGE-SORT(A, p ,q)
    MERGE-SORT(A, q + 1, r)
    MERGE(A, p, q, r)

不斷將陣列拆分成兩個子陣列，之後再作合併

合併排序在上進行操作，不斷地向上推進，合併以排序的子陣列。

以下為C++實作

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;
void merge(vector<int> &A, int, int, int);
void merge_sort(vector<int> &A, int, int);
int main(void)
{
    ios::sync_with_stdio(0), cin.tie(0);
    int A[10] = {2, 4, 1, 6, 7, 3, 9, 0, 3, 1};
    vector<int> array(A, A + sizeof(A) / sizeof(int));
    cout << "Original" << '\n';
    for(auto i : array)
    {
        cout << i << ' ';
    }
    cout << "After merge_sort << '\n'";
    merge_sort(array, 0, 9);//放入起始index和結束index
    for(auto i : array)
    {
        cout << i << ' ';
    }
}

void merge(vector<int> &array, int front, int mid, int end)
{
    vector<int> Left_sub(array.begin() + front, array.begin() + mid + 1);
    vector<int> Right_sub(array.begin() + mid + 1, array.begin() + end + 1);

    Left_sub.insert(Left_sub.end(), INT_MAX);
    Right_sub.insert(Right_sub.end(), INT_MAX);

    int Left_index = 0;
    int Right_index = 0;

    for (int i = front; i <= end; i++)
    {
        if(Left_sub[Left_index] <= Right_sub[Right_index])
        {
            array[i] = Left_sub[Left_index];
            Left_index++;
        }
        else
        {
            array[i] = Right_sub[Right_index];
            Right_index++;
        }
    }
}

void merge_sort(vector<int> &array, int front ,int end)
{
    if (front < end)
    {
        int mid = (front + end) / 2;
        merge_sort(array, front, mid);
        merge_sort(array, mid + 1, end);
        merge(array, front, mid, end);
    }
}

C語言實作

#include <stdio.h>
#include <stdlib.h>
void printArray(int *arr, int size);
void mergeSort(int *arr, int head, int tail);
void merge(int *arr, int head, int mid, int tail);

int main(void) 
{
    int arr[] = {2, 4, 5, 7, 1, 2, 99, 3, 6, 0};
    int size = sizeof(arr)/sizeof(arr[0]);
    
    printArray(arr, size);
    mergeSort(arr,0,9);
    printArray(arr, size);
}

void merge(int *arr, int head, int mid, int tail)
{
    int lenA = mid - head + 1;
    int lenB = tail - (mid + 1) + 1;
    int *leftSub = (int*)malloc(sizeof(int) * (lenA + 1));
    int *rightSub = (int*)malloc(sizeof(int) * (lenB + 1));
    
    int leftIndex = 0;
    int rightIndex = 0;
    
    for (leftIndex = 0; leftIndex < lenA; leftIndex++)
        leftSub[leftIndex] = arr[head + leftIndex]; 
    for (rightIndex = 0; rightIndex < lenB; rightIndex++)
        rightSub[rightIndex] = arr[mid + 1 + rightIndex]; 
    leftSub[lenA] = INT_MAX;
    rightSub[lenB] = INT_MAX;
    
    
    leftIndex = 0;
    rightIndex = 0;
    
    for(int writePointer = head; writePointer <= tail; writePointer++)
    {
        if (leftSub[leftIndex] <= rightSub[rightIndex])
            arr[writePointer] = leftSub[leftIndex++];
        else
            arr[writePointer] = rightSub[rightIndex++];
    }

}

void mergeSort(int *arr, int head, int tail)
{
    if (head < tail)
    {
        int mid = (head + tail) / 2;
        mergeSort(arr, head, mid);
        mergeSort(arr, mid + 1, tail);
        merge(arr, head, mid, tail);
    }
}

void printArray(int *arr, int size)
{
    for(int i = 0; i < size; i++)
        printf("%d ",arr[i]);
    printf("\n");
}

分析分治演算法

當一個演算法包含呼叫自身遞迴時，我們會使用遞迴關係式去描述他所花費的時間。

分治法運行時間的遞迴關係式來自分解，合併，解決這三個步驟。假設為規模為n的一個問題所需要的運行時間。如果問題的規模足夠小時，如對某個常數，，則直接求解即需要常數時間，我們用 Θ表示。假設我們將原問題分解成個子問題，每一個子問題的規模都是原問題的(對於合併排序來說，a和b皆為2)。為了求解一個規模為的子問題，需要的時間，所以需要的時間來解決個子問題。如果將原問題拆分成多個子問題需要的時間，合併多個子問題的解成為原問題的解需要的時間，那麼得到以下遞迴關係式 :

合併排序分析

雖然合併排序在輸入陣列不是偶數也同樣可以作用，但是，假定原問題的規模是，那麼我們可以對遞迴式的分析進行簡化。每一步的分解都會剛好產生出的兩個子陣列。其實我們這樣的假設不會影響到遞迴式的量級，後續會詳細說明。

下面我們分析建立合併排序n個數的最壞情況的運行時間的遞迴式。合併排序一個元素需要常數時間。當有個元素時，我們分解運行時間如下:

• 分解 : 分解步驟僅需要知道子陣列的中間位置，需要常數時間，因此Θ
• 解決 : 遞迴的求解兩個規模均為的子問題，需要的時間
• 合併 : 具有n個元素的子陣列MERGE過程需要Θ的時間，所以Θ

當為了分析合併排序的運行時間而將和函數相加時，我們是把一個函數Θ和另一個Θ函數相加。得出來的結果是一個n的線性函數，也就是Θ，再將這個函數和解決的部分相加，得到以下最差運行時間的遞迴關係式

常數代表合併排序規模為1的問題所需要的時間。

下圖展示了如何求解遞迴式，假設剛好為。
(a)部分展示
(b)部分展示一棵被擴展成描述遞迴式的樹。表示樹根(遞迴的最頂層)，根的兩個子樹為較小的遞迴式
(c)部分展示再被拆解的過程。在第二層的遞迴中，兩個子節點中所需的運行時間為，不斷分截直到規模下降到1
(d)部分展示了整個遞迴樹，並推出結果

高度為，總共有層，整體時間為(表示)，表示為Θ

我們將每一層所需要的運行時間相加，頂層為，下一層為不斷下去，我們會觀察到每一層所需的運行時間皆為。

在輸入規模大約30以上時，merge sort就要比insertion sort來的更快了。

參考資料: 合併排序法, Introduction to algorithms 3rd