So, I need an enum with what is effectively a "none of the above variant". The question is whether to build this into the enum itself or use an option. That is,
I'm leaning towards using Option<Order>. Both because it's less like reinventing the wheel and, above all, because it becomes more compatible with other interfaces. Having two different representations of non-existence will require some form of conversion if they are to be used together, and not having to do that is nice.
I would most likely go with the other alternative if Unordered was more different from plain lack of a particular order.
On the other hand, if you have a database which has options like "return data in date order, return data in id order, or return data in whatever order is fastest", something like "Order::Unordered" probably makes more sense.
If Unordered is exceptional case, then Option.
Otherwise, if Unordered is processed on par with other cases, then make it part of enum.
That's how I would choose.
I'd agree with target_san, it depends on what you do when something is unordered.
Looking at your code fragment above, you have a clear_ordering method which makes it sound like unordered is a valid state, and therefor shouldn't be treated any differently than NewestFirst, OldestFirst, and Id.