Closed
Description
AFAIK Ord
is a trait "for values that can be compared for a sort-order" (quoted from doc) and is distinguished from total ordering (TotalOrd
). Sometimes it seems to be regarded as partial ordering. (cf. @cmr's comment at #7765.)
However, some sort algorithms assume that x ~ z
if x ~ y
and y ~ z
. (a ~ b
here means !(a < b) && !(a > b)
. this relation is called equivalent or incomparable.) Without the assumption, in worst case O(N^2) comparison is needed to sort N elements. Strict partial ordering with this assumption is called strict weak ordering.
I think it is necessary to clarify what we require to impls for Ord
: partial ordering (probably minimum requirement), weak ordering, or something else.
See also: #8360
Metadata
Metadata
Assignees
Labels
No labels