diff options
| author | Matthias Krüger <matthias.krueger@famsik.de> | 2023-05-27 00:23:59 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-05-27 00:23:59 +0200 |
| commit | 18398ad337996ba85e3a8f641e4a3d65f28b1833 (patch) | |
| tree | 4db43a79a2d67cb31d98d15ec1de518d30337d1f | |
| parent | e7068ff8192948f991c5e725a3464037f0d7d349 (diff) | |
| parent | ea327915d8d2311b03e50c12fd2e9e6aa86f0077 (diff) | |
| download | rust-18398ad337996ba85e3a8f641e4a3d65f28b1833.tar.gz rust-18398ad337996ba85e3a8f641e4a3d65f28b1833.zip | |
Rollup merge of #111973 - Sp00ph:update_current_impl, r=Amanieu
Update current implementation comments for `select_nth_unstable` This more accurately reflects the actual implementation, as it hasn't been a simple quickselect since #106997. While it does say that the current implementation always runs in O(n), I don't think it should require an FCP as it doesn't guarantee linearity in general and only points out that the current implementation is in fact linear. r? `@Amanieu`
| -rw-r--r-- | library/core/src/slice/mod.rs | 10 |
1 files changed, 6 insertions, 4 deletions
diff --git a/library/core/src/slice/mod.rs b/library/core/src/slice/mod.rs index bd1b16e8d73..1f195555229 100644 --- a/library/core/src/slice/mod.rs +++ b/library/core/src/slice/mod.rs @@ -3005,8 +3005,9 @@ impl<T> [T] { /// /// # Current implementation /// - /// The current algorithm is based on the quickselect portion of the same quicksort algorithm - /// used for [`sort_unstable`]. + /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also + /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for + /// pivot selection, which guarantees linear runtime for all inputs. /// /// [`sort_unstable`]: slice::sort_unstable /// @@ -3056,8 +3057,9 @@ impl<T> [T] { /// /// # Current implementation /// - /// The current algorithm is based on the quickselect portion of the same quicksort algorithm - /// used for [`sort_unstable`]. + /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also + /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for + /// pivot selection, which guarantees linear runtime for all inputs. /// /// [`sort_unstable`]: slice::sort_unstable /// |