• bearophile <bearophileHUGS lycos.com> May 15 2009
• Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> May 15 2009

bearophile <bearophileHUGS lycos.com> writes:

Sean Kelly:

The built-in sort uses an internal stack rather than recursion, which makes its
performance on a best-case dataset hard to beat.<


The built-in sort is snail slow, and its stack overflows if your array isn't
small:

void main() {
    auto a = new uint[0x8F_FFFF];
    a.sort;
}

So the current built-in sort is bad, and it must be fixed or removed.

Bye,
bearophile
(Sorry for the answering delay, I was busy for about a week. Tons of posts to
catch up!)

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

bearophile wrote:
 Sean Kelly:
 
 The built-in sort uses an internal stack rather than recursion, which makes
its performance on a best-case dataset hard to beat.<


 The built-in sort is snail slow, and its stack overflows if your array isn't
small:
 
 void main() {
     auto a = new uint[0x8F_FFFF];
     a.sort;
 }
 
 So the current built-in sort is bad, and it must be fixed or removed.


That pretty much settles it. Seeing sort's fixed stack, I had this 
feeling for a while, but only now I saw the proof :o).

Andrei