Re: [glob2-devel] okay to release!

[Kai Antweiler]

> std::sort is implementation defined. gcc uses a sort of combination
> based sort, introsort on low numbers of elements (which is pretty much
> anything glob2 would use) and different sorts, like merge sort or
> quick sort, on higher numbers of elements.

I've looked into the stl documentation.  They use introsort (which is
an extremely good choice).  They used quicksort before.  And if they
find something better they will change again.  They never wrote anywhere
how the results for elements with the same key looks.  So even if it
doesn't use randomness now, it might be in the future.  Or there might
occur deterministic changes in the future like Steph wrote. 
So please use std::stable_sort!


>> Random choices are common in sorting algorithms.
>> e.g: a simple quicksort implementation without random choices
>> performs very poor some data.
>> Choosing the pivot elements randomly guarantees mostly good
>> performance for every input.
>
> Some sorting algorithms. In a direct comparison when two elements are
> the same, I doubt a single algorithm will use a random choice.

Trust me.  I like algorithms.  And I took some lectures on this topic.
Quicksort is a standard example how a deterministic choice can
cause serious speed losses.  With some inputs it performs really bad.
If a certain scenario calls quicksort with "bad" inputs often,
you'll get slow execution.
Even an stupid shuffling of the input will repair that.  After that it
is unlikely that quicksort will have to run with even one "bad" input.


There is potential to improve without randomness.
But randomness is generally very usefull in a lot of cases where
you wouldn't expect it.


> I have never heard of this, its just unnecceccarry overhead when
> just leaving them in current order doesn't affect how sorted the
> list becomes, and will be faster than taking the time to generate a
> random binary number and move the elements if nesseccarry.

No.  Sorry randomness is very important and I'm glad I spent so much
time studying it.  But in the beginning I thought the way you do.
It's because you're not used to think in probabilistic terms.

-- 
Kai Antweiler