linux 核心的 list_sort 實作考量 在 linux 核心的 list_sort 使用 buttom-up merge sort 實作排序，buttom-up 與 top-down 的差異在於 buttom-up 少了 partition 這一步驟。 此作法可以省去 recursive 和 stack 的使用（會佔用大量記憶體的寫法，並且會較常去 catch 記憶體更新 cache 內容） 其效能比較根據如下（q_sort 為 lab0-c 實作之排序）： q_sort#nodecache-missesbranchesinstructionscontext-switch1000346977,9884516,04010100003,3403621,93744305,89500100000543,05326326,21194,3295,3471010000007491,55474,6974,191731,6153,305510 list_sort#nodecache-missesbranchesinstructionscontext-switch1000248977,7798519,92400100004,1257614,20284329,38450100000439,19226258,06964,3642,0292310000005824,68914,6028,350731,6579,34489

contributed by < SPFishcool > 開發環境 $ neofetch --stdout fico@fico-mac ------------- OS: Arch Linux ARM aarch64 Host: Apple MacBook Air (13-inch, M2, 2022) Kernel: 6.2.0-asahi-11-1-edge-ARCH Uptime: 16 hours, 7 mins

contributed by < SPFishcool > 開發環境 $ neofetch --stdout OS: Ubuntu 22.04.1 LTS x86_64 Host: GL552VW 1.0 Kernel: 5.15.0-60-generic Uptime: 13 hours, 20 mins Packages: 1877 (dpkg), 9 (snap) Shell: bash 5.1.16

contributed by < SPFishcool > 開發環境 $ neofetch --stdout fico@fico-mac ------------- OS: Arch Linux ARM aarch64 Host: Apple MacBook Air (13-inch, M2, 2022) Kernel: 6.1.0-asahi-2-2-ARCH Uptime: 12 mins

contributed by < SPFishcool > 測驗一 運作原理 程式裡 next_pow2(x) 要找出最接近且大於等於 x 的 2 的冪次方的值。 在改寫程式裡，有著幾行類似下方的程式碼。 x |= x >> 1; 這會讓 x 右移一位並將 1 set 到原本的 x 上，例如： 00100000 變成 00110000、 00100110 變成 00110111。

contributed by < SPFishcool > 測驗一 運作原理 此為快速排序法，其程式碼分析如下： 程式開始時宣告兩個 list_head 為 list_less 與 list_greater，兩者為快速排序時依照 pivot 分類其他節點加到這兩條 linked list 上。 //initial two heads struct list_head list_less, list_greater;