# 2021q1 Homework1 (lab0) ###### tags: `linux2021` Info: https://hackmd.io/@sysprog/linux2021-lab0 Origin: https://github.com/sysprog21/lab0-c ## Contents - In-place merge sort implementation ## Merge Sort 1.0 ### Concept The key of merge sort algorithm is by using a **merge** function that turns two **sorted partition**s of size $(0, M]$ into one sorted partition of size $(0, 2M]$, we can produce a $N$ sized sorted list by starting from partition size of $1/N$, and merge it all the way up. #### Virtual Partition / Counted Iterator When implementing merge sort for linked list, a **virtual partition** that takes up a very small $O(1)$ memory can be created using **Counted Iterator (CI)**: ```c struct counted_iterator { list_ele_t* next, long long remaining } inline list_ele_t* ci_next(struct counted_iterator* ci) { if (ci->remaining == 0) return NULL; if (!ci->next) { ci->remaining = 0; return NULL; } list_ele_t* ret = ci->next; ci->remaining--; ci->next = ret->next; return ret; } ``` A CI will return the next element normally unless an initially specified `remaining` count of elements have been returned. For example, given an initial value of 4, fifth call of `ci_next(A)` will returns `NULL`. ```graphviz digraph { node [shape=record]; llist [label="<i0>a|b|c|d| <i4>r|x|y|z"]; "<CI> A"->llist:i0; "<CI> B"->llist:i4; } ``` #### Slot ~~Machine~~ The **merge** function will compare `next(A)` and `next(B)`, and insert the smaller element to a **slot**. This allows us to handle different target using a same logic. ```graphviz digraph { node [shape=record]; rankdir = "LR" queue [label="{<head>head|size}|queue_t"]; lele [label="{value | <next>next}|<elem>list_ele_t"]; slot -> queue:head; slot -> lele:next; lele:next -> list_ele_t; queue:head -> lele:elem; } ``` We can then do `*slot = <pointer to list_ele_t>` to update the `head` field of `queue_t` or `next` field of `list_ele_t`. #### Skip Size / Partition Size The term **skip size** comes from the number of elements to skip starting from the head of `A` to reach the head of `B`. This guarantees that virtual partition `A` will have exactly `skip_size` elements. ### Algorithm #### Description * Iterate through skip size of $1, 2, 4 ... N$: * Initialize `cur = q->head` * Initialize `slot = &q->head` * When there's more than `skip_size` elements left: * Initialize CI `A = {cur, skip_size}` * Skip `skip_size` elements to find head of `B` * Initialize CI `B {bhead, skip_size}` * When `a = ci_next(A)` and `b = ci_next(B)` is not `NULL`: * `*slot = min(a, b)` * `slot = &(*slot)->next` * Put remaining items in A and B into slot and update accordingly * `cur` is set to whatever that's after the original tail of partition `B` * Put remaining $(0,$ `skip_size` $)$ items into slot * *end of iterA* #### Invariants 1. At the end of *iterA* every `2 * skip_size` elements are sorted within its own virtual partition.