Take the 2-minute tour ×

I was using the built-in sort function of Matlab:

[temp, Idx] = sort(M,2);

I would like to have the sorted index of each row of M, which is a matrix of size > 50k.

I searched hard but did not find anything.. It would be greatly appreciated if you have any comments!

share|improve this question
add comment

4 Answers

up vote 8 down vote accepted

To get a sense of how much room for improvement you have, I would suggest writing a test program in C and use qsort or in C++ and user sort and carefully time it on 7000 inputs of size 7000 (or whatever setup you have in Matlab).

I'm going to give you my estimate: probably Matlab's sort runs (on properly vectorized code, like yours) as fast as C++, and you're just seeing the effect of running an algorithm that takes O(n^2 log n). It is reported in Matlab's marketing material that its sort function was faster than C's qsort, but take it with a grain of salt.

share|improve this answer
+1. Matlab's sort implementation is multithreaded, and C's qsort is not, so it's totally plausible that for larger input arrays Matlab's would be faster. (mathworks.com/support/solutions/en/data/1-4PG4AN/…) (Though to be fair, it's not really right to say you're faster than "C's qsort"; that's a functional spec; you're just faster than a particular libc's implementation of it.) –  Andrew Janke Aug 11 '11 at 15:06
Thank you all for your advice, I guess I would just have to find a work around to my current method and avoid sorting the entire matrix.. –  Hypnos Aug 11 '11 at 19:51
So, I went and benchmarked it with a little MEX function, and Matlab's sort was indeed faster than qsort. Ran it on random or sorted arrays of various sizes between 10 and 500000 elements. Matlab sort was about 4x or 5x faster than qsort on my quad core machine. (Windows XP x64, Matlab R2009b, Visual Studio 2005.) Surprising. –  Andrew Janke Aug 31 '11 at 15:27
add comment

The best way to speed up that sort is to get a faster computer. It will speed everything else up too. :)

The fact is, you can rarely speed up a single call to something like a sort. MATLAB is already doing that in an efficient manner, using an optimized code internally. (Reread the carlosdc answer.) The things you can sometimes get a boost on are tools that are written in MATLAB itself.

So, what can you do? Short of buying that new computer, you can look at your overall code. One single sort of that size is never that big of a problem. But the reason for doing that sort over and over again is. Think carefully about the code, about whether you can change the flow or avoid a many times repeated sort. Algorithm change is often a FAR bigger source of improvement than the wee bit you would ever get even if you could improve that sort.

share|improve this answer
add comment

Sorting is fundamentally O(n log n).

As long as you have a reasonably efficient implementation, this is unlikely to change much.

That said, as Andrew Janke's comment suggests, multi-threading can improve things dramatically.

GPU programming can be a way to get massive speedups. If you have R2010b or later, you may be able to use accelerated versions of built-in functions like sort from Mathworks.

Otherwise, write a mex wrapper around the CUDA Thrust library which includes a sort.

share|improve this answer
add comment

You could write your own sort function in C/C++ as MEX. MATLAB documentation has examples for it.

There exist many sort algorithms which are better then other in edge cases, for example almost sorted data or stability (which does not matter in MATLAB because all its types are value types).

Is your data numeric or strings? For strings there are probably special algorithms for ASCII sort, sometimes natural sort is preferable.

share|improve this answer
add comment

Your Answer


