In quicksort, we can have many different pivot methods. When comparing the probability between two pivot methods (first element pivot, and median of three elements) our probability of choosing a good pivot changes.

Is my math correct for the probability of choosing a good pivot?

We define good pivot as an element that is not in the lower 25% and not in the upper 25% of the array.

If we know that an array of integers IS in random order, then first element pivoting will give us a "good" pivot element 50% of the time. the array is in random order so the odds are always 50/50.

looks like so

[ 1/4 bad | 1/2 good pivots | 1/4 bad ]

When choosing a pivot based on a three element median we can say that the probability looks like this for each choice.

Where x is the size of the list. This equation converges to 1/8

We can assume that the only way to get a bad pivot is where all three elements picked are "bad", 2 low bad and when 2 high bad pivots are picked.

making the median of 3 random elements a good pivot selection 75% of the time.

1/8+1/16+1/16= 1/4 bad pivot options or 25% of the time you will get a bad pivot.

rl 0