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

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-02-07 08:37 -------
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.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
      Known to fail|                            |tree-ssa
   Last reconfirmed|0000-00-00 00:00:00         |2004-02-07 08:37:18
               date|                            |


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