avoid toLower in std.algorithm.sort compare alias

[Jonathan M Davis]

On Saturday, April 21, 2012 20:36:18 bearophile wrote:
> Jonathan M Davis:
> > I'm not sure if it's
> > an order of magnitude worse than your solution though, since it's been a
> > while since I studied Big(O) notation (doing the conversion only once is
> > still more expensive than not converting, but I'm not sure how much more
> > expensive - it might cost less than sort such that it actually doesn't
> > matter as for as Big(O) goes though).
> 
> Performing the toLower every time the cmp function is called doesn't change
> the O complexity.

Yes it does. It adds a loop to each comparison (two loops actually, but since 
they're not nested, Big(O) only cares about the one), since toLower has to 
loop over all of the characters. As sort loops over each of the strings to 
compare them for moving them into a sorted position or not, it calls toLower, 
which adds a nested loop, so it increases the Big(O) complexity. Something 
like this

foreach(str; strings)
    str < otherStr;

becomes

foreach(str; strings)
{
    foreach(dchar c; str)
        //lower characters

    foreach(dchar c; otherStr)
        //lower characters

    str < otherStr;
}

though that's obviously very pseudo-code-ish and not exactly what sort does. 
Regardless, those extra loops when the comparison happens are nested and 
therefore increase the Big(O) complexity of the overall algorithm.

- Jonathan M Davis