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.

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?

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:

N=1e7;
r=floor(randn(N,1)+1i*randn(N,1))+.5+.5*1i;
tic;[~,j]=sortrows([abs(r) angle(r)]);rs1=r(j);toc
tic;rs2=sort(r);toc
isequal(rs1,rs2)

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

r=randn(N,1)+1i*randn(N,1);

where all absolute values are different so that no angles would have to be computed, does not help at all. In contrast, the sortrows-solution computes only N absolute values and N angles.

With a bit of m-code reshaping, this could be generalized to work also for N-dimensional 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

sortrows([real(r) imag(r)]);rs1=r(j);

As sort is a built-in function, it is beyond me to make these changes. It would be probably easy to rename the built-in to _sort_ and pull the checking for complex inputs (and the input validation) to an m-code 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.