Auto merge of #38961 - steveklabnik:fix-sort-wording, r=alexcrichton

Fix wording around sort guarantees

Fixes #38524

/cc @rust-lang/libs @stjepang

1 files changed, 36 insertions, 11 deletions

diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index e704f400d49..fc49c9f5643 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -1064,8 +1064,17 @@ impl<T> [T] {
 
     /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`.
     ///
-    /// This sort is stable and `O(n log n)` worst-case, but allocates
-    /// temporary storage half the size of `self`.
+    /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
+    ///
+    /// # Current implementation
+    ///
+    /// The current algorithm is an adaptive, iterative merge sort inspired by
+    /// [timsort](https://en.wikipedia.org/wiki/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.
     ///
     /// # Examples
     ///
@@ -1083,11 +1092,19 @@ impl<T> [T] {
         self.sort_by(|a, b| a.cmp(b))
     }
 
-    /// Sorts the slice, in place, using `f` to extract a key by which to
-    /// order the sort by.
+    /// Sorts the slice using `f` to extract a key to compare elements by.
+    ///
+    /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
+    ///
+    /// # Current implementation
     ///
-    /// This sort is stable and `O(n log n)` worst-case, but allocates
-    /// temporary storage half the size of `self`.
+    /// The current algorithm is an adaptive, iterative merge sort inspired by
+    /// [timsort](https://en.wikipedia.org/wiki/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.
     ///
     /// # Examples
     ///
@@ -1105,11 +1122,19 @@ impl<T> [T] {
         self.sort_by(|a, b| f(a).cmp(&f(b)))
     }
 
-    /// Sorts the slice, in place, using `compare` to compare
-    /// elements.
+    /// Sorts the slice using `compare` to compare elements.
+    ///
+    /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
+    ///
+    /// # Current implementation
+    ///
+    /// The current algorithm is an adaptive, iterative merge sort inspired by
+    /// [timsort](https://en.wikipedia.org/wiki/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.
     ///
-    /// This sort is stable and `O(n log n)` worst-case, but allocates
-    /// temporary storage half the size of `self`.
+    /// Also, it allocates temporary storage half the size of `self`, but for short slices a
+    /// non-allocating insertion sort is used instead.
     ///
     /// # Examples
     ///
@@ -1535,7 +1560,7 @@ fn merge_sort<T, F>(v: &mut [T], mut compare: F)
 
     // FIXME #12092: These numbers are platform-specific and need more extensive testing/tuning.
     //
-    // If `v` has length up to `insertion_len`, simply switch to insertion sort because it is going
+    // If `v` has length up to `max_insertion`, simply switch to insertion sort because it is going
     // to perform better than merge sort. For bigger types `T`, the threshold is smaller.
     //
     // Short runs are extended using insertion sort to span at least `min_run` elements, in order