How to speed up 'sort' function in Matlab?

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 开发者_StackOverflowsize > 50k.

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

---

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.

---

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.

---

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.

---

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.