Quicksort with 3-way partition

Question

What is QuickSort with a 3-way partition?

Answer 1

http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf

See also:

http://www.sorting-algorithms.com/quick-sort-3-way

I thought the interview question version was also interesting. It asks, are there four partition versions of quicksort...

Answer 2

Picture an array:

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0

A two partition Quick Sort would pick a value, say 4, and put every element greater than 4 on one side of the array and every element less than 4 on the other side. Like so:

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5

A three partition Quick Sort would pick two values to partition on and split the array up that way. Lets choose 4 and 7:

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9

It is just a slight variation on the regular quick sort.

You continue partitioning each partition until the array is sorted. The runtime is technically log₃(n) which varies ever so slightly from regular quicksort's log₂(n).

Answer 3

if you really grind out the math using Akra-Bazzi formula leaving the number of partitions as a parameter, and then optimize over that parameter, you'll find that e ( =2.718...) partitions gives the fastest performance. in practice, however, our language constructs, cpus, etc are all optimized for binary operations so the standard partitioning to two sets will be fastest.