運用 radix sort 的概念加速 sleep sort

偶然從 shakalaca 那看到《排序算法 Sleep Sort》, 剛看完程式碼我的第一印象是: 你在開玩笑嗎? 這在排什麼刁。再仔細看看, 查覺背後神祕的運作原理後, 心中的感覺和文中描述一模一樣: “我擦，真TMD排序了！”。原諒我直接貼上文中的粗話, 當時心中的震撼只能用這樣的字眼才能表達出來。

後來看到留言有人提到這其實是 radix sort 的變型。仔細想想, 確實是這麼一回事!! radix sort 原本是將數字對應到空間的位置, 而 sleep sort 是對到時間上的位置 (或照 sleepnova 的說法, 其實是轉交給 OS 的 task schedule 去排, 不過這樣想就不好玩啦)。所以, 可以套用 radix sort 的概念來加速 sleep sort。

於是憑著愚蠢熱血的餘韻, 用 python + thread 寫了一版程式貼在 github, 有興趣的人可以玩玩看, 排得又「快」又準!! 算時間複雜度不太有意義, 改算秒數比較實在。假設沒有調快執行速度 (即 FASTER_RATE = 1), 且計算時間遠小於 sleep 的時間, 那麼, 若最大允許的正整數是 2**32 - 1, 也就是一個十位數, 我目前的實作方式只需要 90 秒 (比原版快了47721858.83 倍!!)。這樣看來改用二進位會更快, worst case 只要 32 秒 啊!!