`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 n)。这可能会有所回报，因为迭代变得比原始迭代更快。

sort 对于小数组应该更快，而 sort_by 对于大数组表现更好。理论上。

---

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

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