I want to maintain that, from the point of view of abstract mathematics, an order relation is just a binary relation with specific properties. That is, you could define your own order on, e.g., the real numbers which is equivalent to the conventional order with the exception that 5<=x for all positive x. That's a perfectly valid order, every sorting algorithm would happily sort your numbers according to this order (5 would come before 3, if both are in your input data, but that's consistent), and when you perform unique(), you would get exactly the same unique elements as with every other order relation (only in a different order, of course).
Naturally, there is not much reason why anyone would want to define such an order, because there is a natural order on the real numbers that follows from the order on the natural numbers (which naturally derives e.g. from the Peano construction) and that fulfills the laws how arithmetic operations affect order (e.g. a<b <=> a+c<b+c).
So it is possible to extend this order relation all the way from the naturals to the integers to the rationals to the real numbers, fulfilling said laws. However, it is not possible to extend it to the complex numbers: consider the law that a>b => (a* c>b* c if c>0 and a* c<b* c if c<0). Assume b=0, a=i and c=i. If we choose i>0, then we have a>0, but we have a* c=i* i=1, which would also need to be greater than zero because c>0, which is a contradiction. See also https://proofwiki.org/wiki/Complex_Numbers_cannot_be_Totally_Ordered (where the title is misleading, there is just no ordering compatible with the multiplication law).
This is the reason that you often find "you cannot compare complex numbers for order" when you search for it. That's nonsense, of course you can, you could also define an order on the set {"Mickey", "Donald"} by setting "Mickey"<"Donald". Then you have a<b iff a=="Mickey" and b=="Donald". Octave wants to have a total order on the complex numbers, which I accept, because it allows for the standart implementation of unique() to directly work on complex values.
But for defining an order relation on the complex numbers, some choices have to be made, corresponding to which laws of ordering relations under arithmetic operations should be conserved. And, by the way: "total order" means that if a!=b we have either a<b or b<a. This is what we want, and by the way what Matlab according to their documentation does not do, as they compare only the real part (i.e., neither 1<1+1i nor 1>1+1i should evaluate to true, and of course also not 1==1+1i).
There seem to be two main contenders: either lexicographic order, where a<b == (real(a)<real(b))((real(a)==real(b))&&(imag(a)<imag(b))), or absbased order, where a<b == (abs(a)<abs(b))((abs(a)==abs(b))&&(arg(a)<arg(b))).
I argue for lexicographic order, because this keeps the law a<b <=> a+c<b+c for any a,b,c, and further because it allows Octave's narrowing operation (that is, seeing a complex number with zero imaginary part as a real number) to be an order embedding https://en.wikipedia.org/wiki/Order_embedding. Indeed, there is even a trivial arxiv paper on it https://arxiv.org/abs/1003.4906  I did not check it in detail, but its main claims seem valid. Under absbased order, this is no order embedding. I find this problematic, because it can lead to subtle bugs, when a few entries in a large vector become complex and thus completely change the ordering relations on it.
Let's see how other environments to it:
Octave, as we all know, uses absbased order.
Matlab is inconsistent, it uses absbased order for sort, max and min, but compares only the real part (that is, not even lexicographic order) when < or > is evaluated directly.
R, according to comment 15 on bug #52919, uses lexicographic order.
All the other environments I could think of that define complex numbers refrain from defining an order, including Fortran, C, C++ and Python. That's actually what I would do also, so that programming errors that lead to complex values where there should be none raise errors sooner, and if anybody wants to actually compare or sort complex values, to do it explicitly.
As to the comments: Michael Godfrey, both in this thread and in bug #52919 you seem to be much in favour of absbased order, commenting on R using lexicographic order as "Looks like they have not given it much thought". Perhaps R inherited it just from S, as Octave inherited a host of decisions from Matlab, but I have to admit that I also seem to have given it not much thought as I fail to see why it should be obvious that lexicographic sorting can only be chosen due to lack of thought. Further, you postulate "For complex the ordering is a measure of distance in the complex plane" (here should be inserted "distance from zero", as the distance from any other point would also give a perfectly welldefined ordering relation). But this postulate implies already the solution: of course, when you want to order by the distance from zero, you do argbased sorting. My point is that "the order of any two complex numbers is inherited from the order of the nearest real numbers" is an equally valid postulate. What we want to do here is to collect arguments for both possibilities. And how Knuth would sort complex values is beside the point, of course he would sort them as he orders them (I would actually expect him to discuss sorting algorithms only in terms of generic sets with total order). So we are back at having to deliberate which identities we want our order to fulfill.

I am splitting up bug #52919. Now to the most fundamental issue:
When Octave compares complex numbers, it first compares the absolute values and then the phase angle (proviso bug #53011). For sorting, the same comparison is used.
When Matlab compares complex numbers, it only considers the real part. For sorting, it does the same as Octave. Thus, Matlab is not consistent.
Octave wants to be consistent, and it wants to be compatible with Matlab. Obviously, this is impossible, there are two internally consistent choices and one compatible choice. As I will argue now, I would find the other consistent choice better than the current one.
Actually, there is another criterion where it would be nice to be consistent, which is how complex numbers with zero imaginary part are treated with respect to comparison. Indeed, there is the concept of promotion and narrowing (for the latter see bug #52919). Consider the following code:
a is created and the two negative elements are smaller than zero. When now any value inside a is made complex, the whole vector a is promoted to class complex, which changes the ordering relations, and no value is smaller than zero (because the absolute value is now compared). When you only consider a subset where every value has an imaginary part equal to zero, this vector is again narrowed to class real, and everything works as before, the same when you set the one complex value to real. I argue that this is also an issue of internal inconsistency, because the result of the comparison of some elements depends on the value of other elements (and when you have negative numbers, this really is an issue). As far as I understand, Matlab is consistent in this regard, as it only considers the real part, thus real numbers are a subset of complex numbers with consistent ordering in this regard. Another nice consequence of the Matlabordering is that it follows always from a<b that a+c<b+c, whatever a, b and c (real or complex  for Octave only one of the three needs to be complex to potentially violate this law).
So Matlab's ordering (which could be complemented by an imagbased ordering to break ties on the real part and thus give a total order) has in my view more nice properties than the absbased ordering. If Octave switched to it (both with respect to comparison as well as sorting), it would stay halfcompatible, it would stay consistent with respect to ordering and comparison, and it would become more consistent (or at least intuitive, that is, less time taken for hunting programming errors) with respect to seeing real numbers as special case of complex numbers.
In fact, as I am not at all convinced that it is a good idea to blindly compare complex numbers at all, for me it is not so important how the ordering relations are defined on them. But what would help me was to introduce a warning when I compare complex numbers, because I cannot remember ever doing this intentionally. Rather, this would be a hint for a programming error on my part and would have already saved me a few hours bughunting. Thus, when it should be the consensus that it is a bad idea to change the ordering relations on complex numbers at a whim, please consider this as a feature request for such a warning (I see only unique as a valid use case for comparing complex numbers, so there it should probably suppressed, if this is possible).
