owned this note
owned this note
Published
Linked with GitHub
# D05: list
contributed by < `workat60474` >
## 生日悖論
### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
* 以下是生日悖論的表述：
你認為房間裡至少要有多少人，才能讓其中任意兩人同一天生日的機率超過一半( 超過50% )──也就是說，任意兩人生日相同的機率比不同來得高？
事實上，房間裡只需要 57 個人，就可以讓任意兩人同一天生日的機率超過 99％。也就是說，只要 57 個人，就幾乎能確定其中有兩個人同一天生日！這個答案聽起真是令人難以置信。若只針對問題來回答，任意兩人生日相同的可能性比不同還高（也就是機率超過 50% ）所需的人數則遠低於 57。事實上，只要 23 個人就足夠了！
* 以下是生日悖論的數學機率計算：
* 任選第 1 個人令其為 no.1
* 任選第 2 個人令其為 no.2 ， 則 no.2 和前一個人（no.1） 生日錯開的機率為 $\frac{364}{365}$
* 任選第 3 個人令其為 no.3 ， 則 no.3 和前一個人（no.1, no.2） 生日錯開的機率為 $\frac{363}{365}$
* 任選第 4 個人令其為 no.4 ， 則 no.3 和前一個人（no.1, no.2, no.3） 生日錯開的機率為 $\frac{362}{365}$
* 依此類推，我們可以將這 23 人和前人生日不同可能的機率相乘，可以得到這 23 人彼此生日都不同的機率：
* $1*$$\frac{364}{365}*$ $\frac{363}{365}*$ $\frac{362}{365}*...$ $*\frac{343}{365}*$ =$0.4927...$
* 於是當房間裡有 23 人時，房間裡任意兩人生日在同一天的機率便為：
$1－0.4297＝0.5073＝50.73$%
### Birthday problem 對資訊安全的影響在哪些層面？
* 閱讀： [生日攻擊](https://en.wikipedia.org/wiki/Birthday_attack)
* 將上述的生日悖論用以找尋 hash collision 的方法，將在房間裡的每個人看作是 hash funtion 的 input(funtion 中的 domain) ，而每個人的生日則是該 hash funtion 的對應 output (funtion 中的 co-domain)，由上述的生日悖論可知，假設 domain 的範圍為 0-365，只要嘗試 57 次不同 hash value 的就有超過 99% 的機會發生 hash collision 。
* 由於 birthday attack 的關係， hash value 的數值長度如果過短會被視為是不安全的。
* 而關於生日攻擊的防禦辦法，通常透過 增加 hash value bits ，來減少 collision 發生的可能， 讓經由生日攻擊找到 collision 的機率降低。
### 像是 Random Number Generator 這樣的產生器，是否能產生「夠亂」的亂數呢？
* 多數的亂數產生器，都是採取偽亂數（Pseudorandomness），或稱偽隨機性。
* 在電腦中產生「隨機」數字的演算法，由於電腦本身是非常「循規蹈矩」的東西，程式按照同一個輸入值不可能產生兩個輸出值，所以電腦最多只能產生「偽裝」隨機的數字，故名「偽亂數產生器」。
真正的隨機亂數得具備
1.均勻性（uniformity）
2.獨立性（independency）
* 用來計算偽亂數的函數被稱為隨機函數，使用隨機函數產生隨機數的演算法稱為亂數生成器。
* 因為通常在產生亂數時，會需要透過 seed (亂數種子，比方說取時間作為亂數種子)，故亂數也會因此具有範圍。
* 參考：[偽亂數與 P vs. NP](https://medium.com/@_.__/%E5%81%BD%E4%BA%82%E6%95%B8%E8%88%87-p-vs-np-75b205956a0c)
* 參考：[隨機函數](https://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E5%87%BD%E6%95%B0)
## Linux 風格的 linked list
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* function call 在呼叫時：
* 將 function 參數存入暫存器或記憶體，並調整 stack pointer，將參數值 push 到 stack。
* 將控制權轉移給該 function （跳至該 function）
* 取得該 function 所需資料，透過將 資料從 stack 中 pop。
* 執行該 function
* 存取執行結果
* 再次調整 stack pointer，並跳回 callee
* 以上代表 funtion call 所需要的成本。
* 而 Macros 為 pre-processed（前置處理器），透過在編譯前將 macro 在 程式中展開，不必像是函式呼叫經歷上述的成本，缺點是程式經過編譯後，檔案較大，且除錯較不易進行。
* functions are not preprocessed but compiled.
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
1. file-system inode:[linux/fs/inode.c](https://github.com/torvalds/linux/blob/master/fs/inode.c)
* inode 是 UNIX file-system 中的一個重要結構，主要用途是記錄 file-system 中所有檔案以及目錄，也就是說 process 得透過這些 inode 的搜尋才能讀取到所需要的檔案資料，不僅如此，磁碟中的可用空間分配以及檔案配置也都必須透過 inode 的存取來完成。
```clike=
void inode_init_once(struct inode *inode)
{
memset(inode, 0, sizeof(*inode));
INIT_HLIST_NODE(&inode->i_hash);
INIT_LIST_HEAD(&inode->i_devices);
INIT_LIST_HEAD(&inode->i_io_list);
INIT_LIST_HEAD(&inode->i_wb_list);
INIT_LIST_HEAD(&inode->i_lru);
__address_space_init_once(&inode->i_data);
i_size_ordered_init(inode);
}
```
Unix 檔案系統中每個檔案或是目錄都是由單個 inode 所描述，每個 inode 在一個檔案系統中都會有唯一的數字辨識，其中記錄著與檔案或是目錄相關的資訊，檔案的最後修改時間，存取權限，與檔案類型等相關資訊。
inode 所使用的是多層次的索引，在每個 inode 中都會有一個陣列指向多個區塊，這些區塊中的資料可能是檔案的真正的資料或是索引，而其就是利用 linked-list 作為串接使用。
如：
```clike=
struct inode {
unsigned long i_ino;
umode_t i_mode;
uid_t i_uid;
gid_t i_gid;
kdev_t i_rdev;
loff_t i_size;
struct timespec i_atime;
struct timespec i_ctime;
struct timespec i_mtime;
struct super_block *i_sb;
struct inode_operations *i_op;
struct address_space *i_mapping;
struct list_head i_dentry;
...
struct list_head i_devices;
...
}
```
舉上述程式碼 inode 中包含了 `struct list_head i_dentry;` 這個 member ，用以連接 file-system 中的目錄項串列(串連所有與這個 inode 相關的目錄項-dentry )，事實上在這裡所描述的`struct list_head i_dentry;` 和文件裡面的 dentry 結構有些不同，dentry struct 中有一個指向inode的指標。dentry 與inode 所描述的目的是不同的，因为一個 file 可能對應多個file-link。
所以dentry struct 代表的是虛擬意義上的 file 以及其屬性。而inode struct 所代表的是物理意義上的 file 以及其物理上的屬性；可以被看作是一種多對一的關係。這是因為一個已經建立的檔案可以被連接 (link) 到其他檔案。 dentry中還有個d_parent指向父目錄的dentry結構。
2.[linux/mm/slab.c](https://github.com/torvalds/linux/blob/master/mm/slab.c)
kernel 在運作時，常常需要動態配置記憶體給一些 kernel 內的資料結構，但是這些資料結構並不適合用對偶式系統（Buddy System Algorithm，對偶式系統每次都會最少配置一個 frame page 讓 kernel 使用），因為如果資料結構所需要的記憶體大小只要幾百個 bytes， 配置給 kernel 一個 frame page(透過 getconf PAGE_SIZE 可查詢) 會顯得浪費，而 slab allocator 其可解決此問題。
slab allocator 將資料視為物件，將有配置請求的記憶體根據物件的大小等分後，再配置給物件去使用。
Slab allocator 不會自己釋放一個空的 Slab 所佔用的 frame page，只有在 kernel 需要新的 page frame 而對偶式系統無法滿足，而且所有包含在 Slab 裡的物件都未被使用的情況下，空的 slab 才會被釋放。
而當尋找尚未使用的 frame page 時，會挑選某個快取中的空 Slab ，並把該 Slab 從 Slab 的 cache list 中刪除，最終將Slab 連同裡頭的物件一起銷毀，這樣 kernel 就回收了一個 frame page。
```clike=
static void slabs_destroy(struct kmem_cache *cachep, struct list_head *list)
{
struct page *page, *n;
list_for_each_entry_safe(page, n, list, lru) {
list_del(&page->lru);
slab_destroy(cachep, page);
}
}
```
3. [linux/include/linux/timer.h](https://github.com/torvalds/linux/blob/master/include/linux/timer.h)
* 核心計時器(timer)的重點與使用方式
* 可以將核心的工作延後到指定的時間後執行
* 只要初始化，指定到期時間，設定到期時要處理的函式與要傳給函式的參數就可以使用
* 到期 (expired) 後會執行指定的函式，並且不會重複執行
```clike=
struct timer_list {
/*
* All fields that change during normal runtime grouped to the
* same cacheline
*/
struct hlist_node entry; /* timer-list 中的的 node */
unsigned long expires; /*到期值，以 jiffies 為單位*/
void (*function)(struct timer_list *); /* 到期時會執行的函式 */
u32 flags;
#ifdef CONFIG_LOCKDEP
struct lockdep_map lockdep_map;
#endif
};
```
```clike=
void add_timer_on(struct timer_list *timer, int cpu)
{
struct timer_base *new_base, *base;
unsigned long flags;
BUG_ON(timer_pending(timer) || !timer->function);
new_base = get_timer_cpu_base(timer->flags, cpu);
/*
* If @timer was on a different CPU, it should be migrated with the
* old base locked to prevent other operations proceeding with the
* wrong base locked. See lock_timer_base().
*/
base = lock_timer_base(timer, &flags);
if (base != new_base) {
timer->flags |= TIMER_MIGRATING;
raw_spin_unlock(&base->lock);
base = new_base;
raw_spin_lock(&base->lock);
WRITE_ONCE(timer->flags,
(timer->flags & ~TIMER_BASEMASK) | cpu);
}
forward_timer_base(base);
debug_activate(timer, timer->expires);
internal_add_timer(base, timer);
raw_spin_unlock_irqrestore(&base->lock, flags);
}
```
* add_timer_on 其功能為在 cpu 上開始啟動 timer
* `struct timer_list *timer` 代表被加入 list 中的 timer
* ` int cpu` 將啟動該 timer 所在的 cpu
* timer_pending() 可以判斷 timer 目前是否已被加到 list 中，若在等待中會傳回 1
* 在更改 timer_base 時利用，spinlock 來鎖定，避免 race condition。
### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
* typeof 為 c 語言中的 compiler-extension，可以將其用作傳回某個變數， funtion 的 return-type 使用，而且可以根據 typeof 傳回的型別作為宣告使用。
`extern int foo();`
`typeof(foo()) var;`
### 解釋以下巨集的原理
```
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
* 參考：http://blog.udn.com/2768717191/25366271
* 其功能為：透過取得某一個指向 struct 之中的任一成員 (member) 之 pointer， 來得到指向整個 struct 的 pointer。
* 首先 ` const __typeof__(((type *) 0)->member) *__pmember = (ptr);`
* ptr 代表指向 struct 之中的任一成員 (member) 之 pointer
* `__typeof__(((type *) 0)->member) *` 用以取得該 member 的型別，用以宣告指向該 type 的 pointer pmember
* `(type *) 0)->member` 中的 `0` 的寫法是因為：若是寫成 `(type *)->member` 會造成 syntax error（因為 (type *) 不是 valid instance ），透過 0 讓其對 NULL 做 dereference (對 pointer to zero 做dereference)，藉此取得 instance。
* 參考 ：https://stackoverflow.com/questions/18554721/how-to-understand-size-t-type-0-member
* `offsetof `，定義在 `<linux/stddef.h>` 中
* `#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)`
* 用以取得 struct 中某個成員相對於該 struct 位址起點的距離 （offset)
* `(type *) ((char *) __pmember - offsetof(type, member)); ` 做完後會得到該 struct 的位址起點。
### 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
* list.h 提供許多 ＿xxx_funtion 用以增加其他 funtion 的彈性以及擴展性並減少程式的重複性，舉 ＿list_add 為例，＿list_add 提供了新增節點的基本動作，我們只要傳入其所指名的參數(new, prev, next),就會執行新增的動作，將 new 節點新增在 prev 和 next 之間，我們可以將 _list_add 包裝在 list_add 和 list_add_tail 內，只需透過簡單改變傳入的參數，就可以定義出兩個不同的 funtion，一概將新增節點的動作交給 _list_add 負責，這麼做可以增加可讀性和簡約性。
### LIST_POISONING 這樣的設計有何意義？
* 參考：[LIST POISONING](https://en.wikipedia.org/wiki/List_poisoning)
* 在 list_del 裡出現了
* entry->next= LIST_POISON1
* entry->prev= LIST_POISON2
* 這麼做是因為，在 _list_del_entry(entry) 的呼叫中，只有改變 entry 的指向讓 entry 離開 list 中，但是未釋放其記憶體空間，若是此時又去存取到該entry next 或是 prev，這是不合理的，因為entry已經從 list 移除，應該將其視為 NULL 記憶體看待。
* 在 marco CONFIG_DEBUG_LIST 的展開定義下：
```clike=
if (WARN(next == LIST_POISON1,
"list_del corruption, %p->next is LIST_POISON1 (%p)/n",
entry, LIST_POISON1) ||
WARN(prev == LIST_POISON2,
"list_del corruption, %p->prev is LIST_POISON2 (%p)/n",
entry, LIST_POISON2) ||
WARN(prev->next != entry,
"list_del corruption. prev->next should be %p, "
"but was %p/n", entry, prev->next) ||
WARN(next->prev != entry,
"list_del corruption. next->prev should be %p, "
"but was %p/n", entry, next->prev))
return;
```
* 透過 LIST_POISON1 和 LIST_POISON2 所定義的位址，可以避免存取到已經被刪除的節點，是安全上的考量。
### linked list 採用環狀是基於哪些考量？
* 省去新增 rear,last 等需要判斷 head 和 tail 這類的情況，如果是 circular，只要往前存取就可以回到 last，增加了開發的方便性。
### list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？
```clike=
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
```
* list_for_each_safe 和 list_for_each 就功能上都是走訪整個 list 。
* 而 list_for_each_safe ，考量到若是我們在透過 list_for_each 走訪 list 時，若是有刪除某個 entry 的行為，會造成 pos 所指向的 entry 其 prev 和 next 分別指向 LIST_POISON1 和 LIST_POISON2 ，而其記憶體所在是 unsafe state ，為了避免這樣的狀況發生，我們多 maintain 一個 n 指向 pos 的 next，這樣一來，即便該 entry 在被拜訪時遭受刪除，也可以在下一個 loop 因為將 n assign 回 pos ，來避免存取到 LIST_POISON 這類不安全的位址。
### for_each 風格的開發方式對程式開發者的影響為何？
* 是透過 API 所提供的 syntax sugar ，將走訪 list 的動作抽象化，讓開發者只需要專注在走訪時的細項處理，將走訪這個行為交給 API代勞。
### 提示：對照其他程式語言，如 Perl 和 Python 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
* 參考[Doxygen](http://nano-chicken.blogspot.tw/2009/07/doxygen.html)
* Doxygen 是一個document generator，可以將程式中的註解轉換成為說明文件。通常我們在寫程式時，或多或少都會寫上註解，如果在寫註解的時候能依據某種格式，接著就可以透過document generator產生出漂亮的文件。
* 其中以 @ 為開頭註明的註解，會被 Doxygen 抓取用以產生說明文件。
### tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* 參考：[先寫單元測試的12個好處！](http://blog.turn.tw/?p=2821)
* 模組化程式，並且將各個模組個別測試，雖然看似麻煩，但是可以幫助工程師釐清 bug 是發生在 fuction 本身，還是 funtion 之間的互相使用上，長遠來看可以幫助工程師在開發大型專案上減少尋找 bug 和 debug 的時間。
### tests/ 目錄的 unit test 可如何持續精進和改善呢？
* 可以透過在 makefile 裡面增加 test 或搭配 script ，來自動化測試，否則當模組龐大且一一需要手動輸入，其實也是一件耗時的事。
* 可以在 /tests 的程式碼中增加 boundary-test 。
* 可參考： [what makes a good unit tests? ](https://stackoverflow.com/questions/61400/what-makes-a-good-unit-test?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa)
## 針對 linked list 的排序演算法
### 對 linked list 進行排序的應用場合為何？
* 適合採取 linked-list ：
* 動態的資料型態：如 memory 使用的變動，透過 linked-list 比起陣列在增加，減少 memory 配置給某個 process 等動作在 run-time 上更有彈性。
* 經常需要進行插入，刪除：在 linked-list 可在常數時間（O(1)）完成，而陣列在增刪上則會需要花費時間對其他資料做 shift。
* 減少記憶體浪費：利用 linked-list 可以在 run-time 動態更改節點數目，不需要像陣列得先預設大小。
* 如 Unix 系統中的 htop 指令，需要排序目前正在運行中的 process 佔用 cpu 的比例，即是在 list 上作 sorting。
### 考慮到 linked list 在某些場合幾乎都是幾乎排序完成，這樣貿然套用 quick sort 會有什麼問題？如何確保在平均和最差的時間複雜度呢？
* 因為 quick sort 會選擇 list 或 array 中的第一個 element 作為 pivot，而 pivot 會用在切割 list，將把比 pivot 小的 nodes 都放在 list 的左半部，而將將比 pivot 大的 nodes 都放在 list 的右半部，並透過 recursive-call 接著各自完成左右兩部份 list的排序，若原先的 list 早已經排序完成，則被選為pivot的第一個 element 可能為 max 或 min 無論是哪一種，會使得切割效果最小（意即在只對 pivot 一個 node 做了切割，其餘的 n-1 個 nodes 所在位置無改變）。
* 這種情況對 quick sort 來說是 worst-case ： 排序的時間複雜度為 O($n^2$)
* 如何避免這種 worst-case 的發生？
* 改採 Randomized Quick sort ：利用亂數選擇 list 或 array 中任一個 element 作為 pivot，進行切割。
* 改採 medium-of-three : 改選 list 中第一個，最後一個，以及中間的 3 個 elements 中，大小介於兩者之間的（也就是中間值）的 elements 作為 pivot。
### 能否找出 Linux 核心原始程式碼裡頭，對 linked list 排序的案例？
* 參考： [linux/lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
* 其為 linux/lib 中實作的位於 linked-list 上的 sorting 程式碼，其採用的是 merge-sort。
* 考慮到上一個問題，若在 linux 中許多會應用到 linked-list 的結構，其所在 list 原本都已經排序好了，套用 quick sort 反而會時常遇到 worst-case，造成時間複雜度為 O($n^2$) ，若採用 merge-sort ，不論是 Best/average/worst case 其時間複雜度都為 O($nlogn$) 。
### 透過 [skiplist](https://en.wikipedia.org/wiki/Skip_list) 這樣的變形，能否加速排序？
* skiplist 透過維護多層的 linked-list 來加速查詢，在最後一層存放的是有著所有的 nodes 的 linked-list ，而其他層的 linked-list 所存放的 nodes 則是最底層的 nodes 的子集合。
* 
* skiplist 對於 查詢，刪除，和插入元素的時間複雜度 為 O($logn$)，這對於經常要進行查詢的排序演算法，如：insertion sort，selection sort 會有複雜度上（理論上）的優勢，但是也會因為需要維護更多空間（更多上層的 sub-list）來換取時間。
### 研讀 [How to find the kth largest element in an unsorted array of length n in O(n)?](https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on)，比照上方連結，是否能設計出針對 linked list 有效找出第 k 大 (或小) 元素的演算法？
```
Select(A,1,n,i):
將具有 n 個 nodes 的 list 分成 ⌈n/5⌉ 個 group
將這 ⌈n/5⌉ 個 groups 各自排序（可利用 quicksort 或 merge sort）
找出 ⌈n/5⌉ 個 groups 中，每個 group 的中位數 ， 再從這 ⌈n/5⌉ 選出的中位數中，再次找出中位數（median-of-medians）
將 m-of-ms=p 作為 pivot 對 list 做排序： partition q=(A,p,n) (代表在 list中 p 到 n 的位置尋找)
k=q-p+1
if(i==k) return list_entry_k
else if(i<k) return Select(A,p,q-1,i)
else return Select(A,q+1,n,i)
```
### linux-list 裡頭 examples 裡頭有兩種排序實作 （insertion 和 quick sort)，請簡述其原理
* insertion sort : 通常分成兩個部分進行（假設是由大排序到小）：
* step 1:選出一個 element ，由這個 element 開始，往前不斷檢視其他 elements，一直往前直到遇到list的開頭，或者檢視到比自己大的 elements。
* step 2: 重複 step 1 直到選出的 elements 已經包含 list 中所有的 elements，此時排序完成。
```clike=
static void list_insert_sorted(struct listitem *entry, struct list_head *head)
{
struct listitem *item = NULL;
if (list_empty(head)) {
list_add(&entry->list, head);
return;
}
list_for_each_entry (item, head, list) {
if (cmpint(&entry->i, &item->i) < 0) {
list_add_tail(&entry->list, &item->list);
return;
}
}
list_add_tail(&entry->list, head);
}
```
* list_insert_sorted：功能相當於 step1，選出 entry，不斷往前檢查有無比自己大的其他 node
* 若有： 將自己插入到該 node 之前。
* 若無： 代表該 entry本身為該 list 中之最大值，將自己插入 list 末端。
```clike=
static void list_insertsort(struct list_head *head)
{
struct list_head list_unsorted;
struct listitem *item = NULL, *is = NULL;
INIT_LIST_HEAD(&list_unsorted);
list_splice_init(head, &list_unsorted);
list_for_each_entry_safe (item, is, &list_unsorted, list) {
list_del(&item->list);
list_insert_sorted(item, head);
}
}
```
* list_insertsort：功能相當於 step2，利用 list_for_each_entry_safe ，確保在遍歷所有 entry 的同時，對 entry 做刪除不會使程式存取到不安全記憶體。
* 完成時，list 會由小排到大。
* quick sort
```clike=
static void list_qsort(struct list_head *head)
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move(&item->list, &list_greater);
}
list_qsort(&list_less);
list_qsort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
* 首先，利用 list_first_entry 選出 list 中第一個 entry 作為 pivot entry。
* 接著把比 pivot 小的 element，放進 list_less 的前端，而大於等於 pivot 的則放進 list_greater 的後端。
* 接著將 list_less 和 list_greater 傳入下次的遞迴呼叫，一直到 list_is_singular ( list 只有一個 entry) 或者 list_empty(list 無 entry)，作為終止遞迴呼叫的條件。
* 終止遞迴呼叫之後再將其 merge 成為由小排到大的 list。
* 例：
```
head -> 3 -> 2 -> 5 -> 1 -> 4 -> 6
| |
- - - - - - - - - - - - - - - -
pivot : 3
list_less :
1<-2<-list_less
| | => pivot : 1 , list_greater -> 2 => merge ＝> head -> 1 -> 2
- - - - - - - | | | |
- - - - - - - - - - - - - - - -
list_greater:
list_greater -> 5 -> 4 -> 6
| | => pivot : 5, list_gerater -> 6 4 <- list_less
- - - - - - - - - - - - - - | | | |
- - - - - - - - - - - - - - -
=> merge => head -> 4 -> 5 -> 6
| |
- - - - - - - - -
=> merge => head -> 1 -> 2 -> 4 -> 5 ->6
| |
- - - - - - - - - - - - - -
```
## 實作 merge sort，並且在 tests/ 目錄提供新的 unit test
Sign in with Wallet
