After a few searching on the net, I've found an algorithm that seems to be promising:

http://www.dhu.edu.cn/dhuhomepage/dhuintro/kexueyanjiu/paixu/FastPSORT.cpp

I cannot do a proper test since I have no idea about C++. Can someone do the benchmarking for it?