关于rust的内置sort()方法

根据文件:

sort :

当前实施

当前的算法是一种自适应的迭代合并排序,灵感来自 timsort . 它被设计成在切片几乎被排序的情况下非常快,或者由两个或多个排序的序列一个接一个地连接在一起。

此外,它分配的临时存储只有self的一半大小,但对于短切片,则使用非分配插入排序。

至于标准库的其余部分和整个编译器,源代码是 available on GitHub .

sort_unstable :

当前实施

当前的算法基于 pattern-defeating quicksort orson-peters将随机快速排序的快速平均情况与heapsort的快速最坏情况相结合,同时在具有特定模式的切片上实现线性时间。它使用一些随机化来避免退化的情况,但是使用一个固定的种子总是提供确定性的行为。

它通常比稳定排序快,但在一些特殊情况下除外,例如,当切片由多个连接的排序序列组成时。

来源也是 available on GitHub .

(重点是我的)

标准答案是,我想,读一下这本精美的手册;-)

https://doc.rust-lang.org/std/primitive.slice.html#current-implementation-3

是的,可以通过单击 src 链接在每一个文件项的右侧。对于 sort 方法,这将导致:

https://doc.rust-lang.org/src/alloc/slice.rs.html#206-210

它使用一个 merge_sort 此处定义的函数:

https://doc.rust-lang.org/src/alloc/slice.rs.html#888-990