Clarify Ord's requirement: what is needed for sort-order

[omasanori]

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

[omasanori]

In #8357, @thestinger told me Container could use the default methods of Ord if T is a totally ordered set.
I didn't come up with the case weak ordering is not enough but I agree that total order is enough.

[bluss]

I think we need Eq + Ord for lexical order for sequences and tuples. I'm testing out some code

https://gist.github.com/anonymous/17b1b418713e676d5cea

I think we need to, for every Ord relation R, do

`[x, ..xs] R [y, ..ys]  =  if x != y { x R y } else { xs R ys }`

which means, find the first nonequal element pair, and their comparison is the result.

[omasanori]

@blake2-ppc Great. I think Eq is not necessary if R satisfies transitivity of incomparability (the assumption in sammary), though.

https://gist.github.com/omasanori/6188497

[huonw]

Triage: still unclear; #10320 is one possible solution (just make Ord a total ordering and remove the separate TotalOrd trait); it's not clear that #10320 will be accepted so I'm leaving this open for now (if it isn't accepted then we will need to define the type of ordering).

[thestinger]

#12517 can cover this as part of renaming and fixing the incorrect documentation and incorrect generic code.

[omasanori]

Thank you.