[ https://issues.apache.org/jira/browse/STDCXX-397?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12492690 ] Joshua Lehrer commented on STDCXX-397: -------------------------------------- Here is code which creates a killer set then sorts it, counting the compares. Without our fix, sorting an array of 99,999 elements requires 2,500,299,945 compares. With our fix it takes only 3,521,701. Without our fix, sorting an array of 999 elements requires 252,945 compares. With our fix it takes only 21,148. //begin code #include #include #include #include //default comparison with operator< but counts compares struct MyCompare { MyCompare(unsigned int &compares) : m_compares(compares) { } template inline bool operator()(const T& lhs, const T&rhs) { ++m_compares; return lhs indicies; indicies.reserve(mx); for (int i=0; i The algorithm, as implemented, uses real recursion and tail recursion. > First, the pivot is selected, the pivot is done, and the algorithm has a left and a right half, hopefully balanced. > Consider what happens for the LEFT half, which is done using tail recursion. '__last' gets assigned '__cut', then the code goes to the top of the 'for' loop. The test condition of the loop is run, which divides '__max_depth' by two, bringing it closer to zero. > Now consider what happens for the RIGHT half, which is done using real recursion. The function is called recurisvely on the right. __max_depth is NOT cut in half. > What would happen if a poor pivot was selected causing the right half to be large and the left half to be small? What if that happens again and again? The real-recursion case is failing to decrement __max_depth until it starts working on the left half. You can see how if the algorithm continually built right-halves that were relatively large that __max_depth never gets decremented, and the algorithm never detects that it has made LogN recurisve calls. > I believe the proper fix is as follows: > // David R. Musser's Introspective Sorting algorithm > // 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; ) { > if (0 == __max_depth) { > __partial_sort (__first, __last, __last, > _RWSTD_VALUE_TYPE (_RandomAccessIter), __comp); > break; > } > _RandomAccessIter __cut = > __unguarded_partition (__first, __last, > __median (*__first, > *(__first + (__last - __first) /2), > *(__last - 1), __comp), __comp); > // limit the depth of the recursion tree to log2 (last - first) > // where first and last are the initial values passed in from sort() > __max_depth /= 2; > __introsort_loop (__cut, __last, __max_depth, __comp); > __last = __cut; > } > } > "__max_depth/=2" is removed from the "for" loop and placed just above the two recursive calls. > This fixes the worst-case sample set that I have generated. > I look forward to your response, > joshua lehrer > http://www.lehrerfamily.com/ -- This message is automatically generated by JIRA. - You can reply to this email to add a comment to the issue online.