The (*) insertion method is often substituted at deep recursion levels.
The use of 'sentinels' can increase efficiency in this algorithm by avoiding unnecessary checks for overflow in its inner loop. Another efficiency method is the median-of-three technique which avoids worst cases such as large sets of (**) equal numbers or pre-ordered input. In this way a correct pivot selection avoids the O(n2) [big-oh en-squared] worst case for this algorithm. The (*) insertion method is often substituted at deep recursion levels. This algorithm was invented by a British computer scientist working in Communist Russia, Tony Hoare, and works by repeatedly partitioning data about the pivot element in a divide-and-conquer approach. For 10 points, name this algorithm that runs in average O(n log n) time, to perform a particular task with namesake speed.
The use of 'sentinels' can increase efficiency in this algorithm by avoiding unnecessary checks for overflow in its inner loop.
quicksort