關鍵

又把 derivation of radix sort 看一遍，比較知道它在幹嘛了，關鍵仍然落在 stability 的條件上。在 paper 裡面，這個關鍵條件是 map (treesort ds) . ptn d = ptn d . treesort ds。左邊的意思是先用 most significant field 把 input lists 的元素分類（ptn d），然後對每一類用 less significant fields 排序；右邊的意思是先用 less significant fields 把整個 input list 排序過，再用 most significant field 分類。Gibbons 對這個條件的說明是：

Informally, this condition states that ptn d is stable: partitioning a sorted sequence yields a collection of sorted buckets.

讓我想想怎麼 "formally" 說明這件事 XD。

--
明天應該試著把整篇 paper 算一遍才對 XD。

---

好像的確那句 informal explanation 就夠了 XD。