---
title: Divide and Conquer / Merge Sort
tags: 演算法(交大OCW)
---
# 數學歸納法 Induction

這就是 Divide and Conquer 的基礎

## 好處

當你用數學歸納法證明了一個東西，你就無形中建立了一個演算法
因為數學歸納法有要求你每一步要怎麼走要講清楚，而這就是演算法

將一個命題記為 P(n)， n 代表第 n 個步驟；根據證明的形式有兩種歸納法
>命題（英語：proposition）是一個陳述句所表達的判斷，具有真值 by Wiki

## Weak Induction

- Basic Step：要說明 P(0) 為真、是對的
- Inductive Step：假設 P(k) 是對的，進而推導出 P(k+1) 也是對的

其中 P(k) 又叫做 Induction Hypothesis
:::info
因為一次只從一步跳到下一步，所以才叫 weak
:::
## Strong Induction

- Basic Step：要說明 P(0) 為真、是對的
- Inductive Step：假設 P(0)\^P(1)\^...\^P(k) 是對的，進而推導出 P(k+1) 也是對的

:::info
因為一次從很多步跳到下一步，所以才叫 strong
:::

---
:::success
離散數學中會證明兩者等價
:::

## 歸納法小例子 - 貼磁磚

一個 8×8 正方形地板，要鋪磁磚，總共 64 格但有一格有 1 個排水孔不能鋪
請問能不能用一個三角形角塊(Triomino)將整片磁磚鋪完

:::warning
- Triomino請見下面的圖
- 排水孔的位置是任意的
:::

答案是可以的，就是藉由歸納法

最後得到的結論是
:::info
P(n)：任何一個 $2^{n}$ 的正方形地板都可以被 $\frac{2^{n}\times 2^{n}-1}{3}$ 個 Triomino 給貼完 ($n\ge 1$)
:::
:::success
順帶一提，因為 $2^{n}\times 2^{n}-1=(2^{n}+1)(2^{n}-1)$ 並且以 2 = 3 - 1 替換後得到

$$
((3-1)^{n}+1)((3-1)^{n}-1)
$$

當 n 是奇數時，左邊部分會全都剩下 3 的倍數；當 n 是偶數時，右邊部分會全都剩下 3 的倍數
:::
### 1. Basic Step

當 n = 1 時很明顯


### 2. Inductive Step

假設 n = k 的時候是對的

n = k+1 的情況其實就是整塊大的正方形可以看成 4 個小塊的正方形
而這 4 個小塊的正方形，就是我們所假設可以拼得出來的正方形(n = k)

此時只要把這 4 個小正方形中，其中 3 個的排水孔對在一起，形成一個 Triomino ，這樣就可以剛好被一個 Triomino 給補起來；剩下的 1 個小正方形，根據我們的假設，是可以拼出來的

因此 k = n + 1 是可以拼出來的，證明完畢

結論，對於任意正整數，P(n)均成立

:::info
這裡再次可以發現數學歸納法的好處，他除了給你證明，他還給告訴你每一步要怎麼走

在這裡就是指，把 3 個小正方形的排水孔對在一起的步驟
:::

# Divide and Conquer 暖身：Search

不過是指特別情況的 Search；是從一個已排序好的陣列，找出特定值

## Naïve O(n)

直接從頭看到尾，O(n)
這個正確性是顯然的，但就是慢了些

## Binary search O(logn)

每次都選「一個區間」的中間人比較，比完大小就更新區間範圍，然後重複流程

時間就只要 O(logn)

:::info
Binary Search 其實就有使用 DAC，不過屬於比較特殊的情形
:::


理論上「Divide」，也就是分成兩半後，這兩半都要「Conquer」；但是因為陣列已經排過序，所以可以直接藉由比較中間人的大小，判斷出另一半不需要「Conquer」

## Divide and Conquer 步驟

- Divide：將輸入拆解成「很多」「性質一樣的」小部件
- 性質一樣這點很重要；白話上就是「長的一樣」
- 通常會分成兩半
- Conquer
- 遞迴地(Recursively)處理每個小部件，直到可以一眼看出答案才停止遞迴
- Combine：
- 最後，通常也是最難的部分，將每個小部件的解，組合起來


:::warning
步驟上來說就是：
1. Enter the Promblem
2. Divide 1 → Conquer 1 → Combine 1，Enter Conquer 1
3. Divide 2 → Conquer 2 → Combine 2，Enter Conquer 2
4. ...

體會何謂 Recursively
:::

### 複雜度

由於 DAD 通常藉由「遞迴的形式」寫出解法，所以複雜度的分析，也是藉由一個遞迴的關係(Recurrence relation)，表示出上下界

從上面的步驟可以得出

$$
T(Problem)=T(Divide\ 1)+T(Conquer\ 1)+T(Combine\ 1)
$$

## DAC 模板

老師說通常可以用這個模板處理；但是是通常，必要時還是得要依據原則制定內容


---

# Merge Sort - John von Neumann 1945

:::success
- 老師說他在計算機架構等方面的成就令眾人所知，殊不知那個年代的人好像都是通才，他在演算法領域也有很多成就
- 老師說如果你的輸入沒有動任何手腳，你排序的依據是 Comparison Based ，也就是以「比較」作為基礎的話，理論上最快就是 nlogn ，不能再更快了
:::

假設有一堆字母，[A,L,O,G,O,R,I,T,H,M,S]，要將他們依照大小排序


- Divide：將這堆字母拆成兩半
- 拆要拆到最小，直到只剩一個的時候才不拆；這樣才可以直接吐答案

## Pseudo Code


- 可以發現 q 使用地板函數(Flooring functino)，所以另一邊是 q+1
- 使用整數的除法就可以達成
- Mergesort 就是處理遞迴的部分，也就是「Conquer」
- Merge 就是合併的部分，也就是「Combine」
- 可以發現到最後 p = r，就不會進行任何處理

整個步驟流程如下


:::info
其實在做的時候不會左右一起做，而是最左半邊先做完
:::

---

# 複雜度分析

將整體的時間記為 T(n)

- D(n) 就是「Divide」的部分
- T(n/2) 就是遞迴地呼叫自己，也就是「Conquer」的部分，並且 n 變成一半的大小
- C(n) 就是「Combine」的部分

因此最後的整體時間就會寫成

$$
T(n)=D(n)+2T(\frac{n}{2})+C(n)
$$

這就是上面所提到的 Recurrence Relation


## C(n)

D(n) 只要一個步驟就可以結束，所以是 O(1)

理論上排序可以達到 nlogn 的速度，因此希望這個 C(n) 可以達到 O(n) 的速度

那要如何 Merge 呢，請看下圖


- 圖中 AGLOR 跟 HIMST 是已經排好序的兩個小部件(陣列)
- 這兩個小部件要額外建立兩個 index ，記錄目前比較到哪裡
- 用一個額外的陣列來存放結果

:::success
- 兩個小部件的 index 一開始就是 0 ，原因是因為我們要從頭開始比較，也就是比較「他們的最小」，到底誰才更小
- 比較出誰比較小後，讓他所在的陣列所持有的 index 加 1，並把比較小的人放進建立好的額外陣列
- 重複上述過程

當然也要補上是否有部件已經空了的檢查
:::

:::info
假設這兩個小部件各自有 n~1~, n~2~ 個人
那最糟糕的情形就是要比較 n~1~ + n~2~ - 1 次，最後一個剩下的人不用比
不過結果來說就是線性時間 O(n)
:::

---

## T(n/2)

那遞迴的部分要怎麼處理？在數學上有些比較難的、比較複雜的，可以直接查資料，不用自己推導
不過這裡所教的目前都很簡單，可以自己 Handle

### case：n ≦ 2

當遞迴到了最後 p = r ，也就是指 n ≦ 2 的時候，甚麼都不會做，因此是常數時間
用一個常數 c 表示：
$$
T(n)\le c
$$
> n = 1 就是 p = r ；n = 2 會呼叫兩個 T(1)；

### case：n > 2

下面在推導的時候，其實不會先寫 O ，因為 O 代表了「精簡後」，會影響結果；所以這裡要先換成另一個常數 c 乘上 n ，寫作 cn


於是得到
$$
T(n)\le 2T(\frac{n}{2})+cn
$$

:::warning
眼尖的人應該會發現，當初 q 有用地板函式，那這樣照理來說，不應該是2T(n/2)
因為取地板後，奇數個數會使得兩者的大小不一樣
:::

沒有錯，就正確性來說應該要寫成下面這樣


但是如果當 n 很大時，在 Asymptotic Analysis 下，這件事不打緊，不會影響結果
差異非常小，可以直接忽略它；因此如果函式的分析有出現地板根天花板函式(Flooring、Ceiling)，就可以先忽略他們

---

## 兩招處理 Recurrence

### 前置處理
:::info
- 為了找出 Upper Bound，先將 ≦ 換成 =，也就是做最壞的打算
* 並且為了避免要取地板跟天花板，先假設 n 是 2 的某個次方
:::
$$
T(n)= 2T(\frac{n}{2})+cn
$$

## Unrolling the recurrence / Recurrence Tree

:::info
老師說這招很常用
會叫做 Recurrence Tree 是因為會將 T(n) 展開成一個 Tree 的形式
:::

三個步驟：
- Analyzing the first few levels
- 就是先畫出少少的一兩層，並找到規律
- Identifying a pattern
- 畫出整個樹的樣子
- Summing over all levels
- 將每層加起來

### Analyzing the first few levels

將原本的 T(n) 展開個一兩層，找到規律；並且可以知道，總共只要做 logn 次展開


### Identifying a pattern 和 Summing over all levels

Tree 的每個 Node 就代表一個小步驟(一個「Conquer」)，最後就是把每個步驟加起來
每次加起來的時候，要 Level by Level 一層一層的加起來


:::warning
因此最後得到的複雜度總和就是 cn × logn
取 Big O 可以得到 O(nlogn)
:::

---

## Substituting a guess

:::info
利用數學歸納法

先猜一個答案，然後用數學歸納法證明；如果是很有經驗的人，可能很快就找到答案，但是對於經驗不多的人，可能找了很久都沒找到答案
>這不就是通靈嗎
:::

上面所謂的猜答案，就是去猜他的時間複雜度；因為上面我們已經知道是 nlogn了，那這裡我們就猜 nlogn

從上面已知：

$$
Any\ function\ T\ satisfying\ this\ recurrence\ \\
T(n)\le 2T(\frac{n}{2})+cn\ when\ n>2,\ and\ T(2)\le c\\
$$

去猜

$$
is\ bounded\ by\ O(nlog_{2}n),\ when\ n>1
$$

也就是說，我們相信下面這件事

$$
T(n)\le cnlog_{2}n, for\ all\ n\ge 2
$$

n=1 的時候是常數時間

### Base step

已知的部分

$$
k=2,\ T(2)\le c\le 2c = c×2×log_{2}2
$$

### Inductive Step (Strong)

開始猜的部分

$$
T(m)\le cmlog_{2}m\ for\ all\ m<n\ \\
T(\frac{n}{2})\le c(\frac{n}{2})log_{2}(\frac{n}{2})；log_{2}(\frac{n}{2})=log_{2}n-1\ \\
T(n)\le 2T(\frac{n}{2})+cn\le 2c(\frac{n}{2})log_{2}(\frac{n}{2})+cn=cn[log_{2}n-1]+cn=cnlog_{2}n
$$

證明完畢

結論，對於所有 n ≧ 2 均成立

---
:::info
可以注意到，Unrolling 有換掉 ≦ 的步驟，而通靈法則維持 ≦ 的關係
:::

---

# Heap Sort 跟 Merge Sort

通常來說比較常採用 Merge Sort，因為 Heap Sort 基本上依賴陣列取值的方便性
可是如果資料不是以陣列儲存，而是像是 Linked List 之類的話， Heap Sort 就不是一個好選擇
這時候就是 Merge Sort 出場的地方

---

# 久違的手刻 Merge Sort

#include<stdio.h>
#include<stdlib.h>
// sort a int array
// can easily modify some little parts to sort other kinds of array

// the swap function determin ascending or descending
void swap(int left,int right,int* array);
// merge function merge the two parts of array
void merge(int left,int right,int middle,int* array);
// main part of DAC
void mergeSort(int left,int right,int* array);
void pArray(int* array,int length);
int main(int argc, char const *argv[])
{
    int N = 10;
    int array[10] = {3,2,1,6,5,4,9,8,7,10};
    printf("Before\n");
    pArray(array,N);
    mergeSort(N-N,N-1, array);
    printf("\nAfter\n");
    pArray( array,N);
    return 0;
}
void pArray(int* array,int length){
    for (int i = 0; i < length; i++)
    {
        printf("%d ",array[i]);
    }
    
}
void swap(int left,int right,int* array){
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}
void merge(int left,int right,int middle,int* array){
    // start comparing by head of the two parts
    int head_left = left;
    int head_right = middle + 1;
    // a temp array to store sorted elements
    int* temp = malloc(sizeof(int)*(right-left+1)); 
    int temp_index = 0;

    // comparing the tow parts from each first element
    // put the smaller one to the temp array
    while (head_left <= middle && head_right <= right)
    {
        // "=" makes it stable
        // ascending
        if(array[head_left] <= array[head_right]){
            temp[temp_index] = array[head_left];
            temp_index++;
            head_left ++;
        }else{
            temp[temp_index] = array[head_right];
            temp_index++;
            head_right ++;
        }
    }
    // put remaining elements into temp array
    if(head_left<= middle){
        for (int i = head_left; i <= middle ; i++)
        {
            temp[temp_index] = array[i];
            temp_index++;
        }
    }else{
        for (int i = head_right; i <= right ; i++)
        {
            temp[temp_index] = array[i];
            temp_index++;
        }
    }
    
    // copy elements back to origin array
    
    for (int i = left; i <= right; i++)
    {
        array[i] = temp[i-left];
    }
    
    // don't forget deallocate it
    free(temp);
      
}
void mergeSort(int left,int right,int* array){
    // divide the array to two parts repeatedly
    // in the end it there may be one element in each part, which means right - left = 1
    // or left = right, doesn't need to do anything
    if(right-left == 1){
        // ascending
        if(array[left] > array[right]){
            swap(left,right,array);
        }
        return;
    }else if(right-left == 0){
        return;
    }else{
        int middle = (left+right)/2;
        mergeSort(left,middle,array);
        mergeSort(middle+1,right,array);
        merge(left,right,middle,array);
        return;
    }
}