A) A variant of QUICKSORT which returns without sorting subarrays with fewer than k elements and then uses INSERTION-SORT to sort the entire nearly-sorted array (slide 24). B) A variant of QUICKSORT using the median-of-three partitioning scheme. Slide 24: Cutoff to INSERTION-SORT (as in MERGE-SORT). Alternatively:

When calling QUICKSORT on a subarray with fewer than k elements, return without sorting the subarray

After the top-level call to QUICKSORT returns, run INSERTION-SORT on the entire array to finish the sorting process

Taking advantage of the fast running time of INSERTION-SORT when its input is nearly sorted

Tail call optimisation convert the code so that it makes only one recursive call

Usually good compilers do that for us

Iterative version with the help of an auxiliary stack