Analysis of Multi-Pivot-Quicksort

Quicksort is a frequently used sorting algorithm. Its principle is

simple: take one element (the so-called pivot element) and put all

elements smaller than the pivot element into the list of small

elements and all elements larger than the pivot element into the list

of large elements. Then sort both lists recursively and concatenate

the results. Its running time depends on the data and is therefore

random.  The corresponding random variable has been studied

extensively with much work done in the 1970s.

It was quite a surprise when a new variant surfaced which was better

than expected. The clue is to take two pivot elements and to partition

into small, medium and large elements. If we happen to compare a small

element with the smaller pivot element first, then comparing with the

larger pivot element can be omitted. But how do you know with what

pivot element to compare first? For two pivot elements, optimal

partitioning strategies have been found and analysed in the last two

years.

This talk reports on work in progress with Daniel Krenn on the

analysis of multi-pivot quicksort, i.e., several pivot elements are

used.