---
tags: C
---
# Merge K Lists
## 疊代版本
這題要求合併 K 條串列，可以應用在實作 iterative merge sort 的合併階段，將分割好的 sorted lists 合併成一條，如下圖所示
```graphviz
digraph G {
result[label="1|2|3|4|5|6|7|8", shape=record, height=.1]
node31[label="2|5", shape=record, height=.1]
node32[label="4|6|8", shape=record, height=.1]
node33[label="1|7", shape=record, height=.1]
node34[label="3", shape=record, height=.1,width=.4]
node41[label="2|4|5|6|8", shape=record, height=.1]
node42[label="1|3|7", shape=record, height=.1]
subgraph cluster_3 {
style=filled;
color="#a6cee3";
label="sorted lists";
node32;
node34;
node33;
node31;
}
node31 -> node41
node32 -> node41
node33 -> node42
node34 -> node42
subgraph cluster_2 {
style=filled;
color="#b2df8a";
label="merge";
node41
node41
node42
node42
node41->result
node42->result
}
}
```
若要將這題用疊代的方式逐步改進的話有3種方式，
### 方法一: naive
天真的用第一條串列接上剩下的串列，這樣會導致 `lists[0]` 愈來愈長，多數的情況下合併速度會愈來愈慢。不過沒關係，優化往往不是一步到位而是逐步改進。
~~這種寫法多 Submit 幾次或許有機會 faster than 1%~~
```c=
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
if(listsSize == 0)
return NULL;
for(int i = 1; i < listsSize; i++)
lists[0] = mergeTwoLists(lists[0], lists[i]);
return lists[0];
}
```
### 方法二: Two Pointer with Divide and conquer
從固定第一條串列改成頭跟尾兩兩合併直到剩1條為止，比起 naive 每次都用愈來愈長的串列跟另一條串列合併，頭尾合併在多數的情況下兩條串列的長度比較平均，合併會比較快。
當合併完頭尾後，偶數長度會少一半，奇數長度則為 `(listsSize + 1) / 2`，奇數更新的方式也可以用在偶數長度上。
```c=
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
if(listsSize == 0)
return NULL;
while(listsSize > 1) {
for(int i = 0, j = listsSize - 1; i < j; i++, j--)
lists[i] = mergeTwoLists(lists[i], lists[j]);
listsSize = (listsSize + 1) / 2;
}
return lists[0];
}
```
### 方法三: Divide and Conquer
除了用頭尾合併，還可以用間隔來存取下個要合併的串列，分別合併 `lists[i]` 跟 `lists[i+interval]`，為確保內層回圈不會重複存取，索引值 `i` 會更新為 `i + interval * 2 `，當內層回圈合併完之後會把解果分別存到 `lists[interval*2]`, `lists[interval*4]`, `lists[interval*6]`, etc.(如下圖所示) 所以外層回圈在更新 interval 的時候也要變成兩倍，以確保進入內層會圈存取 lists 的正確位置。
```c=
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
if(listsSize == 0)
return NULL;
for(int interval = 1; interval < listsSize; interval *= 2)
for(int i = 0; i + interval < listsSize; i += interval * 2)
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
return lists[0];
}
```
```graphviz
digraph G {
interval1[label="<f0>L0|<f1>L1|<f2>L2|<f3>L3|<f4>L4|<f5>L5|<f6>L6|<f7>L7", shape=record]
interval2[label="<f0>L01|<f1>|<f2>L23|<f3>|<f4>L45|<f5>|<f6>L67|<f7>", shape=record]
interval4[label="<f0>L0123|<f1>|<f2>|<f3>|<f4>L4567|<f5>|<f6>|<f7>", shape=record]
interval8[label="<f0>result|<f1>|<f2>|<f3>|<f4>|<f5>|<f6>|<f7>", shape=record]
interval1:f0 -> interval2:f0
interval1:f1 -> interval2:f0
interval1:f2 -> interval2:f2
interval1:f3 -> interval2:f2
interval1:f4 -> interval2:f4
interval1:f5 -> interval2:f4
interval1:f6 -> interval2:f6
interval1:f7 -> interval2:f6
interval2:f0 -> interval4:f0
interval2:f2 -> interval4:f0
interval2:f4 -> interval4:f4
interval2:f6 -> interval4:f4
interval4:f0 -> interval8:f0
interval4:f4 -> interval8:f0
}
```
## 應用到疊代版合併排序上
[Github](https://github.com/LambertWSJ/list-sort-example)
:::warning
這裡我只應用頭尾合併跟 interval 版本，naive 太慢以至於我無法等待。
:::
merge sort 有兩個階段
分割 list :arrow_right: 合併 lists
分割串列的目的是把串列分成 sorted lists，一般來說是用遞迴加上快慢指標來分割成單一節點，但也可以改成分割出排序好的部份做為 sorted lists。
舉例來說有一串列如下
```graphviz
digraph G {
origin[label="2|5|4|6|8|1|7|3", shape=record, width=.1, height=.1]
}
```
如果要遞增排序，則把串列中遞增的部份分離出來
```graphviz
digraph G {
sorted1[label="2|<tail>5", shape=record, width=.1, height=.1]
sorted2[label="4|6|<tail>8", shape=record, width=.1, height=.1]
sorted3[label="1|7|<tail>3", shape=record, width=.1, height=.1]
}
```
固定好分割串列的方式後，比較頭尾合併跟 interval 版在合併階段的效能。
我套用 [quiz1](https://hackmd.io/@sysprog/linux2021-quiz1) 的程式再做一些修改分別實作下面三種版本的 merge sort
### 遞迴版 merge sort
```c
node_t *mergesort_list(node_t *head)
{
if (!head || !head->next)
return head;
node_t *slow = head;
node_t *fast;
for (fast = head->next; fast && fast->next; fast = fast->next->next)
slow = slow->next;
node_t *mid = slow->next;
slow->next = NULL;
node_t *left = mergesort_list(head);
node_t *right = mergesort_list(mid);
return mergeTwoLists(left, right);
}
void mergesort(node_t **list)
{
*list = mergesort_list(*list);
}
```
### 應用頭尾合併的 merge sort
```c
void mergesort_iter_head_tail(node_t **list)
{
node_t *head = *list;
if (!head || !head->next)
return;
int listsSize = 0;
const size_t n = 100000;
node_t *lists[n];
node_t *sorted = head;
// split sorted lists
while (sorted)
{
node_t *iter = sorted;
while (iter && iter->next)
{
if (iter->value < iter->next->value)
iter = iter->next;
else
break;
}
lists[listsSize++] = sorted;
sorted = iter->next;
iter->next = NULL;
}
// merge K Lists
while (listsSize > 1)
{
for (int i = 0, j = listsSize - 1; i < j; i++, j--)
lists[i] = mergeTwoLists(lists[i], lists[j]);
listsSize = (listsSize + 1) >> 1;
}
*list = lists[0];
}
```
### 應用間隔(interval)來合併的 merge sort
```c
void mergesort_iter_interval(node_t **list)
{
node_t *head = *list;
if (!head || !head->next)
return;
int listsSize = 0;
const size_t n = 100000;
node_t *lists[n];
node_t *sorted = head;
// split list to sorted lists
while (sorted)
{
node_t *iter = sorted;
while (iter && iter->next)
{
if (iter->value < iter->next->value)
iter = iter->next;
else
break;
}
lists[listsSize++] = sorted;
sorted = iter->next;
iter->next = NULL;
}
for (int interval = 1; interval < listsSize; interval *= 2)
{
for (int i = 0; i + interval < listsSize; i += interval * 2)
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
}
*list = lists[0];
}
```
### 測量效能方式
benchmark 參考 [hankluo6](https://hackmd.io/@hankluo6/2021q1quiz1) 同學，將編譯器優化從 o1 到 os，每次執行 1000 回合，每回合排序長度為10萬且不連續的串列，。
### 實驗結果
頭尾合併版跟 interval 版看似只差在合併的順序不同，但是應用在 merge sort 還是有效能上的差異，而且兩種方法階比一般的遞迴版來的快，但我不知道為什麼 interval 版會更快一點？
這樣測量或許不公平，因為我沒有做出遞迴版的 head-tail 跟 interval 來比較，我目前還沒想到怎麼把分割成 sorted lists 的部份改成遞迴，或許明年參加 [Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)時我會想到。
Google Drive
Gist
Clipboard
Sign in with Wallet
