Content deleted Content added
→Properties of pivot: clarity |
|||
Line 111:
=== Properties of pivot ===
The chosen pivot is both less than all and greater than half of the elements in the list of medians, which is around <math>n/10</math> elements <math>(1/2 * (n/5))</math> for each half. Each of these elements is a median of 5, making it less than 2 other elements and greater than 2 other elements outside the block. Hence, the pivot is less than <math>3(n/10)</math> elements outside the block, and greater than another <math>3(n/10)</math> elements inside the block. Thus the chosen median splits the elements somewhere between 30%/70% and 70%/30%, which assures worst-case linear behavior of the algorithm. To visualize:
{|class="wikitable" border=1
| |||