diff options
| -rw-r--r-- | src/liballoc/slice.rs | 7 | ||||
| -rw-r--r-- | src/libcore/slice/mod.rs | 7 |
2 files changed, 14 insertions, 0 deletions
diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs index 33d28bef2d7..2ded376b395 100644 --- a/src/liballoc/slice.rs +++ b/src/liballoc/slice.rs @@ -211,6 +211,13 @@ impl<T> [T] { /// /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case. /// + /// The comparator function must define a total ordering for the elements in the slice. If + /// the ordering is not total, the order of the elements is unspecified. An order is a + /// total order if it is (for all a, b and c): + /// + /// * total and antisymmetric: exactly one of a < b, a == b or a > b is true; and + /// * transitive, a < b and b < c implies a < c. The same must hold for both == and >. + /// /// When applicable, unstable sorting is preferred because it is generally faster than stable /// sorting and it doesn't allocate auxiliary memory. /// See [`sort_unstable_by`](#method.sort_unstable_by). diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs index a50426ba886..c22ea0a01f8 100644 --- a/src/libcore/slice/mod.rs +++ b/src/libcore/slice/mod.rs @@ -1339,6 +1339,13 @@ impl<T> [T] { /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate), /// and `O(n log n)` worst-case. /// + /// The comparator function must define a total ordering for the elements in the slice. If + /// the ordering is not total, the order of the elements is unspecified. An order is a + /// total order if it is (for all a, b and c): + /// + /// * total and antisymmetric: exactly one of a < b, a == b or a > b is true; and + /// * transitive, a < b and b < c implies a < c. The same must hold for both == and >. + /// /// # Current implementation /// /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters, |