Thread Subject: sort almost constant vector and quicksort

Hello,

I got a question about matlab sort function. I know the function sort is based on the quick sort algorithm. However, I think there are also some tricky optimizations.

I wrote a mex-file implementing the quicksort algorithm and when sorting a pure random vector, time execution between both are quite similar :

clear

  Nx = 1000;
  Ny = 1000;
 Xt = uint8(ceil(256*rand(Nx , Ny)));

  tic,[Xs , idx] = sort_features(Xt);,toc
  clear Xs idx;,pack
  tic,[Xs1 , idx1] = sort(Xt , 1);,toc

Elapsed time is 0.236003 seconds.
Elapsed time is 0.279259 seconds.


However if I changed Xt by Xt = zeros(Nx , Ny ); a pure constant vector
then I got

Elapsed time is 3.713831 seconds.
Elapsed time is 0.107564 seconds.

I think in this case, I am in the worst case of the quick sort algorithm.
So I need an advice to choose my sorting algorithm where my data vector is almost a constant one.

Regards,

Sebastien