Obviously you need a PartialOrd (and Ord, PartialEq and Eq) implementation for all fundamental data structures, since otherwise they are unusable (can't sort to canonicalize ordering, sort+uniq, use as btree keys, etc.).

Lexicographic order is the most common choice for vector; the other reasonable choice is length-then-lexicographic.