March 1995/When the "Best" Algorithm Isn't/Table 1

Table 1 Sizes of sorted and unsorted portions of arrays. For each table entry, a smaller unsorted portion results in the special insertion sort outperforming Quicksort, while a larger unsorted portion makes Quicksort the better performer.

               Size of  Size of
               Sorted   Unsorted
Size of Array  Portion  Portion   Proportion
--------------------------------------------
     500         489      11        2.25%
     1000        979      21        2.15%
     2000        1952     48        2.46%
     5000        4900     100       2.04%
     7500        7368     132       1.79%
     10000       9812     188       1.92%
     15000       14692    308       2.10%
     20000       19564    436       2.23%