issorted & sortrows

[Jaroslav Hajek]

hi,

following the recent optimization of sort, I went ahead and
implemented issorted and optimized sortrows:

Summary of changes:
issorted is now supported (built-in). issorted(..., 'rows') also
works, except for sparse matrices.
The check uses no temporary arrays and is quite fast (inlined versions
in octave_sort).

sortrows is still an m-file. The old O(M*N*log(M) + M*N^2) algorithm
has been simply optimized to be O(M*N*log(M)).
The homogeneous case (whole matrix is sorted or all columns
identically oriented), is forwarded to a built-in implementation
(__sortrows_idx__) that uses an even more efficient breadth-first
tree-traversing algorithm, which I think is O(M*(N+log(M))).

To get an idea of the speed-up, here's a short benchmark:

# purely random array
n = 5e5;
a = randn (n, 10);
tic; b = sortrows (a); toc

# partially ordered array
for k = 1:100
  i = ceil (rand * (n-1));
  # swap randomly
  b = [b(j+1:end,:); b(1:j,:)];
endfor
tic; a = sortrows (b); toc

with a recent tip, I got:
Elapsed time is 1.62271 seconds.
Elapsed time is 1.62623 seconds.

whereas with the new tip, I get:

Elapsed time is 0.194896 seconds.
Elapsed time is 0.084264 seconds.

i.e. speed-ups by factors 8.3 and 19.3.

once again I'm wondering whether Matlab has an even better algorithm...

cheers

-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz