CODEWITHSUNDEEP
algorithmsortingrust
Andra
Andra

Reputation: 1392

What sorting algorithm does Rust's built-in `sort` use?

What algorithm is the built-in [T]::sort method using? Is it possible to have a look at the code for that method?

Upvotes: 5

Views: 9473

Answers (2)

Pierre-Antoine
Pierre-Antoine

Reputation: 2094

The standard answer is, I think, Read The Fine Manual ;-)

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

And yes, it is possible to have a look at the code, by clicking on the src link on the right of every documented item. For the sort method, this leads to:

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

It uses a private merge_sort function which is defined here:

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

Upvotes: 3

mcarton
mcarton

Reputation: 30061

As per documentation:

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.

As for the rest of the standard library and the entire compiler, the source is 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.

The source is also available on GitHub.

(emphasis are mine)

Upvotes: 20

Related Questions