Author: sebor Date: Mon Apr 30 13:59:43 2007 New Revision: 533854 URL: http://svn.apache.org/viewvc?view=rev&rev=533854 Log: 2007-04-30 Martin Sebor STDCXX-397 * algorithm.cc (__introsort_loop): Reduced max_depth before each recursive call rather than after. Modified: incubator/stdcxx/trunk/include/algorithm.cc Modified: incubator/stdcxx/trunk/include/algorithm.cc URL: http://svn.apache.org/viewvc/incubator/stdcxx/trunk/include/algorithm.cc?view=diff&rev=533854&r1=533853&r2=533854 ============================================================================== --- incubator/stdcxx/trunk/include/algorithm.cc (original) +++ incubator/stdcxx/trunk/include/algorithm.cc Mon Apr 30 13:59:43 2007 @@ -1104,13 +1104,14 @@ // David R. Musser's Introspective Sorting algorithm +// (see www.cs.rpi.edu/~musser/gp/introsort.ps) // O(N * log (N)) worst case complexity _EXPORT template void __introsort_loop (_RandomAccessIter __first, _RandomAccessIter __last, _Dist __max_depth, _Compare __comp) { - for (; __last - __first > __rw_threshold; __max_depth /= 2) { + for ( ; __rw_threshold < __last - __first; ) { if (0 == __max_depth) { __partial_sort (__first, __last, __last, _RWSTD_VALUE_TYPE (_RandomAccessIter), __comp); @@ -1125,7 +1126,7 @@ // limit the depth of the recursion tree to log2 (last - first) // where first and last are the initial values passed in from sort() - __introsort_loop (__cut, __last, __max_depth, __comp); + __introsort_loop (__cut, __last, __max_depth /= 2, __comp); __last = __cut; } }