`sort_by`的複雜性是什麼？

Question

我想知道sort_by背後的排序算法是什麼，這很複雜。

我正在排序一個嵌套數組，這就是它所做的;從：

arr = [[0,2],[1,1],[3,5],[4,2]] 

我排序它，

arr = arr.sort_by{|x,y|y} 

並且變得：

arr = [[1,1],[0,2],[4,2],[3,5]] 

Answer 1

的sort方法需要ø（Ñ日誌Ñ）。 sort_by方法實現了Schwartzian變換。它增加了的Ô（2 Ñ）的開銷，而實際的排序保持在Ô（Ñ日誌Ñ）。這可能會付出代價，因爲迭代速度比原來的迭代速度快。

sort對於小陣列應該更快，而對於大陣列來說sort_by會更好。理論上。

---

我無法抗拒基準，這裏是結果。數組大小在x軸上，以及在和軸上的排序時間（秒）。數組元素是由SecureRandom.base64(50)創建的隨機字符串。 Ruby版本是1.8.7。

結果表明，sort_by沒有顯著獲得對sort隨着數組大小。