Quick Sort Pivot Head-to-Head Run Times

One important consideration when implementing quick sort is the choose pivot algorithm because it has considerable influence on the actual run time. The charts below show the run times for four different implementations of choose pivot.

  • QUICK_PIVOT_LAST: Always pivot on the last element
  • QUICK_PIVOT_FIRST: Always pivot on the first element
  • QUICK_PIVOT_RANDOM: Pivot on a random number between $0$ and $n - 1$
  • QUICK_PIVOT_MEDIAN: Pivot on the median of the first, last, and middle element

Arrays w/ Random Integer Values

alt text

ALGORITHM n=100 n=1000 n=10000 n=100000
QUICK_PIVOT_LAST 0.000018 sec 0.000278 sec 0.003496 sec 0.039498 sec
QUICK_PIVOT_FIRST 0.000015 sec 0.000221 sec 0.002966 sec 0.019478 sec
QUICK_PIVOT_RANDOM 0.000009 sec 0.000131 sec 0.001513 sec 0.019836 sec
QUICK_PIVOT_MEDIAN 0.000008 sec 0.000105 sec 0.001408 sec 0.018257 sec

Key Takeaways:

  • Their is very little difference but MEDIAN wins by a slight margin. The difference is small enough that a slightly different arrangement could change the result.
  • The run time characteristics of RANDOM are consistent for all types of arrays

Arrays w/ Pre-Sorted Values

alt text

ALGORITHM n=100 n=1000 n=10000 n=100000
QUICK_PIVOT_LAST 0.000100 sec 0.010064 sec 0.521035 sec 51.889364 sec
QUICK_PIVOT_FIRST 0.000010 sec 0.000734 sec 0.067155 sec 6.826175 sec
QUICK_PIVOT_RANDOM 0.000008 sec 0.000126 sec 0.001223 sec 0.015780 sec
QUICK_PIVOT_MEDIAN 0.000006 sec 0.000067 sec 0.000931 sec 0.010826 sec

Key Takeaways of pre-sorted arrays:

  • LAST takes a whopping 51 seconds.

Arrays w/ Reverse Sorted Values

alt text

ALGORITHM n=100 n=1000 n=10000 n=100000
QUICK_PIVOT_LAST 0.000064 sec 0.006450 sec 0.294811 sec 29.853370 sec
QUICK_PIVOT_FIRST 0.000031 sec 0.002881 sec 0.294002 sec 29.855214 sec
QUICK_PIVOT_RANDOM 0.000008 sec 0.000101 sec 0.001344 sec 0.015160 sec
QUICK_PIVOT_MEDIAN 0.000011 sec 0.000773 sec 0.076374 sec 7.544084 sec

Key Takeaways of reverse arrays:

  • LAST and FIRST are equally bad
  • MEDIAN is clearly unacceptable

From this analysis, we can conclude that although MEDIAN has a slight edge for random and sorted arrays, RANDOM is the best general purpose option.

Source Code

Full Repo

Relevant Files:

Click here for details on generating actual run time data