Sorting an array

[Bill Baxter]

Jarrett Billingsley wrote:
> "Bill Baxter" <dnewsgroup at billbaxter.com> wrote in message 
> news:eq8iau$2s4p$1 at digitaldaemon.com...
>> I thought it used a quicksort with insertion sort for the smallest arrays.
>> In fact such a beast seems to be in dmd/src/phobos/internal/qsort.d.
>> Are you sure arrays use the qsort2.d implementation?
> 
> There's apparently some licensing issues with qsort.d?  I'm not entirely 
> sure, but.. well to be honest I'm not sure whether it uses qsort.d or 
> qsort2.d.  I shouldn't have jumped to that conclusion.  Looking at the 
> phobos makefile it seems to use qsort.d, but qsort2.d is also mentioned.
> 
> Either way, it's probably not the fastest, as I wrote a templated 
> _recursive_ quicksort (not even using a stack like the one in qsort.d) that 
> consistently outperforms the builtin one by 5~10% (on my computer at least). 
> 
> 

Yeh, I can believe that.  qsort2 calls the TypeInfo.compare method to do 
its dirty work.  It probably does not ever get inlined.  Whereas a 
templated version can usually inline the compare away.

Funny, that's the #1 thing that Stroustrup has been jumping up and down 
about for years.  It's the first thing he pulls out whenever someone 
says C++ is slow.  No no! He says, look at std::sort!  Faster than C's 
qsort() could ever even hope to be!

--bb