# Lecture 05 - Merge sorting
> 課程內容 : 中興大學資工系 范耀中教授 (112 學年度第 2 學期)
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

## 1. Top-down merge sort
> Basic plan
> * DIvide array into two halves
> * Recursively sort each half
> * Merge two halves

:::info
Merge sort 的核心思想是使用 divide and conquer 的方式將==問題簡化，逐一解決==後再將結果合併
:::


### 1.1 Merge sort demo

* 將原始 Array 切成兩個 sub-Array (`[0:lo, mid:hi]`)
* 排序左邊的 sub-Array(`aux[0:lo]`) 以及 右邊的 sub-Array(`aux[mid:hi]`)
* 依序比較 Left array 的元素(index : i)以及 Right array 的元素(index : j)
* **哪個元素小就回填**原始 Array(index : k)

### 1.2 Java implementation

// copy original array
for (int k=lo; k<=hi; k++)
    aux[k] = a[k];(#)

// merge
int i = lo;      // index of left sub-array
int j = mid + 1; // index of right sub-array

for (int k=lo; k<=hi; k++)
{
    // left array finished, only merge right array
    if (i > mid)
        a[k] = aux[j++];(#)
    
    // right array finished, only merge left array
    else if (j > hi)
        a[k] = aux[i++];
    
    // right element > left element
    else if (less(aux[j], aux[i]))(#)
        a[k] = aux[j++];
    
    // right element < left element
    else
        a[k] = aux[i++];
}    

### 1.3 Animation
* [20 random items](https://www.toptal.com/developers/sorting-algorithms/merge-sort)
* [20 reverse-sorted items](https://www.toptal.com/developers/sorting-algorithms/merge-sort)

### 1.4 Complexity analysis
複雜度分析分為 **拆分(split)** 與 **合併(merge)** 兩步驟來看

#### 拆分

以 size $= N$ 的 Array 為例，需要將原始的大 Array 做拆分，分成 $[\frac{N}{2},\frac{N}{2}]$ 的兩個小的陣列，再將兩個小的陣列切分成 $[\frac{N}{4}, \frac{N}{4}, \frac{N}{4}, \frac{N}{4}]$ 的四個小陣列。直到拆分成 $[1, 1, ...,1]$ 的陣列為止，需要進行 $N-1$ 次的拆分，時間複雜度為 $O(n-1)=n$

#### 合併

**合併的同時也需要完成排序(sorted)**，每次排序的過程中，需要將==所有== sub-Array 的元素從左到右看過一次，並把小的元素放到大 Array 中，**每個回合都需要進行 N 次** ( $\because$ N 個元素)

合併的過程需要進行 $\log N$ 個回合，所以合併的複雜度為 $O(N \cdot \log N)$

整體時間複雜度為 $O((N-1) + N \cdot \log N) = N \cdot \log N$

:::info
合併的過程中，每回合的 sub-Array 元素個數依序為 : $1 \rightarrow 2 \rightarrow 4 \rightarrow ... \rightarrow 2^k$ 且 $N=2^k$，因此總共需要 $k = \log 2^k = \log N$ 的回合數
:::


### 1.5 Improvement
#### 缺點
Merge sort 在排序的過程中，需要將
* 原始的大 Array **複製** (2N for array copy)
* **提出**兩個小 Array 的元素作比較 (2N for comparison)
* 從小的 Array **複製**到大 Array 之中 (2N for move back)

上述過程需要多付出 **6 倍**的 Array access 的成本，以長度為 N 的 Array 來說，就==需要付出 6N 的搬移成本==
([Java demo](#12-Java-implementation) 中有 # 符號的地方)


#### 改善 (1) : Cutoff
當切分成小 Array 的時候，**直接使用 insertion 做排序**。習慣上當只剩下 10 個元素時就直接使用 Insertion sort 做排序

#### 改善 (2) : Stop if already sorted
若兩個小 Array 本身**已經排序好(?)**，則合併過程就不用再排序

如何判斷**已經排序好** :question:
1. 每回合 **merge 前兩邊的小 Array 本身都是已經排好的**
2. 每次 merge 的過程都是比兩邊 array 的最左側元素，所以只需 ==確定左邊陣列的最大值(最右元素) < 右邊陣列的最小值(最左元素)== 就可保證兩個陣列已經排好，合併過程不用再比較


## 2. Bottom-top merge sort
> Basic plan
> * Pass through array, merging sub-arrays if size 1
> * Repeat for sub-arrays of size 2, 4, 8, ...

:::info
針對 size = 1 的 sub-arrays 排序，排完後再對 size = 2 的 sub-array 排序
:::


### 2.1 Natural merge sort
:::info
:bulb: **Idea**
Exploit pre-existing order by identifying naturally-occurring runs
:::

> **Tim sort**
> * Natural merge sort
> * Use **insertion sort** to make initial runs(if needed)
> * A few more clever optimizations

Tim sort(by Tim Peter)所看到的一些事情 :
1. 沒人規定 Array 在拆解的時候 sub-Array 必須要一樣大
2. 任意長度的 Array 可能本身**隱含了一些順序**

:::info
:point_right: 對 Array 做 Linear search 來找出**逐漸遞增**的 sub-Array
:::


## 3. Comparators (比較級)
一個物件有多個 attribute 且欲對多個 attribute 做比較。

許多 programming language 都有提供 comparator 的實作，只要知道概念即可不用記實作細節，需要使用時再查就好

## 4. Stability
> Definition :
> 當單一元素有多個 attributes 時，**對多個屬性排序**後，相對應的**順序會不會亂掉**


### 4.1 Insertion sort : Stable
A 本身已經照順序，B 排序的過程不會影響到 A 的順序

| index $i$ | index $j$ | 0 | 1 | 2 | 3 | 4 |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| 0 | 0 | $B_1$ | $\bf{A_1}$ | $\bf{A_2}$ | $\bf{A_3}$ | $B_2$ |
| 1 | 0 | $\bf{A_1}$ | $B_1$ | $\bf{A_2}$ | $\bf{A_3}$ | $B_2$ |
| 2 | 1 | $\bf{A_1}$ | $\bf{A_2}$ | $B_1$ | $\bf{A_3}$ | $B_2$ |
| 3 | 2 | $\bf{A_1}$ | $\bf{A_2}$ | $\bf{A_3}$ | $B_1$ | $B_2$ |
| 4 | 4 | $\bf{A_1}$ | $\bf{A_2}$ | $\bf{A_3}$ | $B_1$ | $B_2$ |

### 4.2 Selection sort : Not stable

| index $i$ | min | 0 | 1 | 2 |
| :-: | :-: | :-: | :-: | :-: |
| 0 | 2 | $\bf{B_1}$ | $\bf{B_2}$ | $A$ |
| 1 | 1 | $A$ | $\bf{B_2}$ | $\bf{B_1}$ |
| 2 | 2 | $A$ | $\bf{B_2}$ | $\bf{B_1}$ |
| | | $A$ | $\bf{B_2}$ | $\bf{B_1}$ |

### 4.3 Shell sort : Not stable
B 本身已經有順序，對 A 排列的過程中會影像 B 的順序

| h | 0 | 1 | 2 | 3 | 4 |
| :-: | :-: | :-: | :-: | :-: | :-: |
| | $\bf{B_1}$ | $\bf{B_2}$ | $\bf{B_3}$ | $\bf{B_4}$ | $A_1$ |
| 4 | $A_1$ | $\bf{B_1}$ | $\bf{B_2}$ | $\bf{B_3}$ | $\bf{B_4}$ |
| 1 | $A_1$ | $\bf{B_1}$ | $\bf{B_2}$ | $\bf{B_3}$ | $\bf{B_4}$ |
| | $A_1$ | $\bf{B_1}$ | $\bf{B_2}$ | $\bf{B_3}$ | $\bf{B_4}$ |

:::info
基本上只要牽涉到==長距離的移動==，就有可能是 Unstable
:::

### 4.4 Merge sort : Stable
Left sub-array : `[A1, A2, A3, B, D]`

Right sub-array : `[A4, A5, C, E, F, G]`

Merge : `[A1, A2, A3, A4, A5, B, C, D, E, F, G]`

## 5. Summary :star:

:::danger
**inplace** 表示排序過程中==是否需要額外的記憶體空間==，打 :heavy_check_mark: 表示不需要
:::

## Reference
1. [Merge sort](https://medium.com/appworks-school/初學者學演算法-排序法進階-合併排序法-6252651c6f7e)
2. [Sorting animation](https://www.toptal.com/developers/sorting-algorithms)