> This way, we *dynamically* > decide to optimistically start an insertion sort, in the hopes that it > will occasionally prevent a recursion, and worst case the input is > slightly more sorted for the next recursion.
I should mention one detail -- we put a limit on how many iterations we attempt before we give up and partition/recurse. The author's implementation chooses 8 for this limit. The paper mentions this technique in section 5.2, but is not the origin of it. -- John Naylor EDB: http://www.enterprisedb.com
