ruby - `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 方法需要 O(n log n)。 sort_by 方法实现了Schwartzian 变换。它增加了 O(2 n) 的开销，而实际排序保持在 O(n log < em>n).这可能会有所返回，因为迭代变得比原始迭代更快。

sort 对于小型数组应该更快，而 sort_by 对于大型数组执行得更好。理论上。

---

我忍不住要进行基准测试，这就是结果。 x 轴上的数组大小，y 轴上的排序时间(以秒为单位)。数组元素是使用 SecureRandom.base64(50) 创建的随机字符串。 Ruby 版本为 1.8.7。

结果表明，随着数组大小的增加，sort_by 并没有明显优于 sort。