[Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort

[ctsa at u dot washington dot edu]

------- Additional Comments From ctsa at u dot washington dot edu  2004-02-07 22:09 -------
(In reply to comment #1)
Thanks Andrew! This answer was a big help. Apologies for the spurious report...

> I know that this is a performance bug but note the C++ standard says this:
> Complexity: Approximately N log N (where N ==last-first) comparisons on the
"average".
> If the worst case behavior is important stable_sort()(25.3.1.2) or
partial_sort()(25.3.1.3) should be used. 
> 
> And note that stable_sort is faster than both quick_sort and std::sort in your
case which you give.
> Also note that the only complexity is needed to O(N log N) compares on average
and so this is not 
> comforming issue.
> 
> Confirmed that std::sort is much slower than quick_sort and std::stable_sort
in the case you gave, note 
> it might be faster in other cases though.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14061