[cfe-dev] error with lambda function that results in endless loop

[Jean-Daniel Dupas]

Le 3 mai 2012 à 16:07, Howard Hinnant a écrit :

> On May 3, 2012, at 8:54 AM, Jean-Daniel Dupas wrote:
> 
>> According to the following presentation, libc++ is able to detect 8 different patterns when it sort a list:
>> 
>> http://llvm.org/devmtg/2010-11/Hinnant-libcxx.pdf
> 
> Just fyi, there's not a set number of patterns that it looks for.  At every partition it checks to see if it took zero swaps to do the partition, and in this case, it draws a tentative conclusion that if the sequence is already partitioned, it might also be already sorted, or nearly so.  It will try an insertion sort on the sequence in this case since insertion sort on an ordered sequence takes only N comparisons.  If the insertion sort has to do more than a small number of insertions (8 I think), the insertion sort is abandoned, and the quick sort algorithm resumes.
> 
> This checking and switching to insertion sort is done during every partition phase as the quick sort recurses to smaller and smaller sub-sequences.  So as a subsequence becomes "more sorted", it becomes more likely to switch over to an insertion sort, and if successful, short circuits the remaining recursive quick sort decent for that sub-sequence.
> 
> This combination of algorithms will sort an ordered sequence with 2N comparisons and a reverse ordered sequence with 3N comparisons.  The cost of the check is an integer increment with each swap, and a branch on that integer after each partition.
> 
> Howard
> 


Interesting.
Thank you for this information :-)