algorithm - Rust 内置的 `sort` 使用什么排序算法？

Question

built-in [T]::sort method是什么算法使用？是否可以查看该方法的代码？

Answer 1

根据文档:

sort :

Current implementation

The current algorithm is an adaptive, iterative merge sort inspired by timsort. It is designed to be very fast in cases where the slice is nearly sorted, or consists of two or more sorted sequences concatenated one after another.

Also, it allocates temporary storage half the size of self, but for short slices a non-allocating insertion sort is used instead.

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

sort_unstable :

Current implementation

The current algorithm is based on pattern-defeating quicksort by Orson Peters, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on slices with certain patterns. It uses some randomization to avoid degenerate cases, but with a fixed seed to always provide deterministic behavior.

It is typically faster than stable sorting, except in a few special cases, e.g. when the slice consists of several concatenated sorted sequences.

来源也是available on GitHub .

(重点是我的)