You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@stdcxx.apache.org by se...@apache.org on 2007/04/30 22:59:44 UTC
svn commit: r533854 - /incubator/stdcxx/trunk/include/algorithm.cc
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 <se...@roguewave.com>
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 <class _RandomAccessIter, class _Dist, class _Compare>
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;
}
}