Hoare’s Partition, Improved
November 1, 2016
In today’s exercise we will make several improvements to the quicksort program of the previous exercise, working in small steps and measuring our progress throughout. We make the following improvements:
- Move the swap and comparison inline.
- Early cutoff and switch to insertion sort.
- Improved pivot with median-of-three.
All three improvements are well-known. The first improvement eliminates unneeded function-calling overhead. The second improvement reduces the number of recursive calls on very small sub-arrays, replacing them with a sorting algorithm that is well-adapted to nearly-sorted arrays. The third improvement improves the likelihood of a good partition and eliminates some cases where the algorithm performs poorly.
Your task is to write an improved quicksort and measure your improvement. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 