I think that's not a bad tradeoff. Peak memory would be 16N (original array) + 16N(temporary array) + 16N(index vector) or 48N. The current solution is probably 16N (original array) + 16N (output sorted array) or 32N. The ratio is only 1.5.
I believe this should be done, but it will require hacking deep in to liboctave. There is both the sorting routine in liboctave/util and then code which calls it out of Array.cc. The code in Array.cc is general and shared by all types that derive from it. If we override each of the Complex object types there are quite a few.
There might be an intermediate ancestor between Array and these final types which could be overridden. That would be ideal because I would rather not repeat the code 11 times.

Yes, it seems you are right, sortrows needs more internal storage than what it needs for the output (this should have been obvious to me). When I limit the available virtual memory for the octave process to 2 GB via bash's ulimit, I can allocate a matrix of dimensions Nx2 with N up to 8.5e7, but I can generate the permutation vector via sortrows only for N=4e7. So it seems that the memory consumption would be 16* N for the input, 16* N for the temporary [abs() arg()], and about 16* N for the generation of the permutation vector (including already the output). That is, going via sortrows the peak consumption is about three times the size of the input, while via the native sort it is about two times.
Probably this cannot be significantly improved anymore, so we have to stick with the time/space dilemma.

That seems right. I was just counting blocks of memory, but being more specific about the sizes of those blocks shows that the overhead is only 25% (5/4).
One of the things to verify, or change, would be to make sure that internally sortrows can form the index vector without also forming the sorted array. If the sorted array must always be generated then the overhead would be 75% (7/4).
When using '~' in the interpreter to discard an output it is the function's responsibility to check for that condition. Some routines don't bother and calculate every single output and then just let the interpreter silently discard the unused ones. That is not ideal, but many routines were coded before the '~' feature was even available.

It's not quite that bad. Remember that this path would only be taken when the input r is complex, and that abs(r) and arg(r) both are real. Thus, when you sort a vector of N complex doubles, you have an input of 16* N byte and generate an output of 16* N byte in the current implementation. Going via sortrows, you generate in addition to the input 16* N temporary bytes, pass it to sortrows, which gives you back an index vector of 8* N bytes. At this point you can clear the temporary [abs(r) arg(r)] and generate the final output of 16* N bytes. So the peak memory consumption relates as 5/4, which is not so critical, I would say (in fact probably even less, because sort uses additional state internally, and I would guess this to be of the same magnitude in both algorithms).
When you request both sorted array and permutation indices, the memory consumption is exactly equal, and when you only request the permutation indices, it will probably be the same (because I would guess that the traditional sort needs at least the same internal storage as the size of the input, even when it only needs to compute the indices).
Have you tested your quoted values of memory requirements, and have I overlooked something?

Confirmed. This is a pretty classic time/space tradeoff. The current solution uses 2N blocks of memory ([1] original array, [2] returned sorted array), but requires on order N log2(N) calculations of abs and a variable number of angle calculations. Using something like sortrows would require 4N blocks of memory ([1] original array, [2] abs (array), [3] angle (array)], [4] sorted index array) but a guaranteed number of N calculations of abs and angle.
An additional possibility is to consider a threshold where smaller arrays use sortrows and larger arrays use the traditional sort routine. Note that the threshold could be quite high. One million complex double values is 16 MB so the sortrows solution would require 64 MB. Most PCs have RAM measured in GB so this wouldn't necessarily be an issue.
I'm attaching an updated test script.
which shows sortrows is ~3X faster.
(file #43111)

I am splitting up bug #52919. Now to the performance of sort on complex values:
Sort is unnecessarily slow on complex values. Consider the following code:
On my computer, the first line takes 2.3 seconds, while the second line takes 8.0 seconds. The results are equal (apart from subtleties that could be introduced as mentioned in bug #53011). Probably, this comparatively low performance is due to sort having to compute two absolute values for each comparison, of which there are about log(N)*N. Indeed, it seems that it does not only compute the absolute value, but also the phase angle (?), because defining
where all absolute values are different so that no angles would have to be computed, does not help at all. In contrast, the sortrowssolution computes only N absolute values and N angles.
With a bit of mcode reshaping, this could be generalized to work also for Ndimensional objects with sorting along a chosen dimension (and thus automatically to an actual sortrows evaluated on complex inputs). Also, Matlab's new option 'ComparisonMethod','real' could of course cheaply be emulated by
As sort is a builtin function, it is beyond me to make these changes. It would be probably easy to rename the builtin to _sort_ and pull the checking for complex inputs (and the input validation) to an mcode wrapper, but as sort is quite fundamental, it is perhaps worth the while to stay on the C++ level.
As I have argued elsewhere, I am not quite convinced that it is a good idea to sort complex values (or even compare them) at all, because if I want to sort on the absolute values, I would explicitly do so, but unique also uses sort and would hence profit from an increased performance, and here it is obviously meaningful to ask for the unique values of a complex vector.
