Quicksort with 3-way partition
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...
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 nlog3(n) which varies ever so slightly from regular quicksort's nlog2(n).