From 7e57f0a6a8fd4e5df7890613918f4a2c3b5a1fb7 Mon Sep 17 00:00:00 2001 From: "Havvy (Ryan Scheel)" Date: Sun, 2 Sep 2018 22:26:38 -0700 Subject: Doc total order requirement of sort(_unstable)_by I took the definition of what a total order is from the Ord trait docs. I specifically put "elements of the slice" because if you have a slice of f64s, but know none are NaN, then sorting by partial ord is total in this case. I'm not sure if I should give such an example in the docs or not. --- src/libcore/slice/mod.rs | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'src/libcore/slice') 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] { /// 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, -- cgit 1.4.1-3-g733a5