  We present numerical results for the probability of bad cases for Quicksort,
i.e. cases of input data for which the sorting cost considerably exceeds that
of the average. Dynamic programming was used to compute solutions of the
recurrence for the frequency distributions of comparisons. From these
solutions, probabilities of numbers of comparisons above certain thresholds
relative to the average were extracted. Computations were done for array sizes
up to n = 500 elements and for several methods to select the partitioning
element, from a simple random selection to what we call "recursive median of
three medians." We found that the probability strongly depends on the selection
method: for n = 500 and a theshold 25% above the average number of comparisons
it ranges from 2.2*10^(-3) to 3.0*10^(-23). A version of Quicksort based on the
recursive median of medians approach is proposed, for which our data suggest a
worst case time complexity of O(n^1.37).
