lib/list_sort.c sort執行流程

起始狀態

且設A<B<C

A = 0x555555566eb8;
B = 0x555555566f68;
c = 0x555555567018;

---

count = 0;

// queue的第一格節點
pending = NULL
list = 0x555555566eb8 // A

list->prev = pending // A->prev = NULL
pending = list // A
list = list->next // B
pending->next = NULL // A->next = NULL

---

count = 1

tail = &pending; // pending point to A

// enter for loop
tail = &(*tail)->prev // tail point to pending->prev (0x555555566eb8)

list->prev = pending // B->prev = A (nothing change)
pending = list // pending = B
list = list->next // list = C
pending->next = NULL // B->next = NULL

---

count = 2

// ready for merge
a = *tail // B
b = a->prev // A

merging

head = NULL
tail = &head

*tail = a; // head = A
tail = &a->next // tail = NULL (go to next term)
a = a->next // a = NULL (go to next term)

*tail = b // A->next = B

after merge

// 被合併的list會由head到tail接好
// 尚未被合併的list會由tail利用prev一路往前接

// 此處應該是在處理順序調換後和原本list相接的部分
a->prev = b->prev // nothing change

list->prev = pending // C->prev = A
pending = list // pending = C
list = list->next // list = NULL (到底了)
pending->next = NULL

list = pending // list = C
pending = pending->prev // pending = A (要併進去的list頭)

prepare for merge remain nodes

// 盡可能地往前合併
next = pending->prev // next = NULL (沒東西能再併了)
// 跳出for loop

merge final

// 將所有剩餘節點合併並串起來
tail = head
count = 0


// 第一次迴圈
// cmp(a,b) < 0

// 重建double linked結構
tail->next = a
a->prev = tail
tail = a

// a轉到下一項
a = a->next

// 第二次迴圈
// cmp(a,b) < 0

// 重建double linked結構
tail->next = a // tail->next = B (A->next = B)
a->prev = tail // B->prev = A
tail = a // tail = B

// a轉到下一項
a = a->next  // a = NULL

跳出迴圈

// 合併剩下還沒被併進去的節點
tail->next = b // B->next = C (直接把剩下還沒合併的接起來)

// enter while loop

// 重建 double linked 結構
b->prev = tail // C->prev = B
tail = b // tail = C
b = b->next; // b = NULL (後面沒東西併了)

跳出迴圈

// 完成tail和head的link
tail->next = head // C->next = head
head->prev = tail // head->prev = C