stdcxx-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From se...@apache.org
Subject svn commit: r533854 - /incubator/stdcxx/trunk/include/algorithm.cc
Date Mon, 30 Apr 2007 20:59:44 GMT
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  <sebor@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;
     }
 }



Mime
View raw message