Begin with the outermost call to quicksort and
suppose that none of these j minus i plus 1 elements is chosen as a pivot.
Where then could the pivot lie?
Well it can only be a pivot that's greater than all of these or
it could be less than all of these.
For example if this is the third fourth, fifth, sixth and seventh smallest elements
in the array, well the pivot is either the minimum or the second minimum in which
case it's smaller than all five elements, or it's the eighth or largest, or
larger elements in the array in which case it's bigger than all of them.
There's no way you're going to have a pivot that somehow is wedged in between
this set because this is a contiguous set of order statistics, okay.
Now what do I mean by these elements leading parallel lives?
Well, in the case where the pivot is chosen to be smaller than all of these
elements, then all of these elements will wind up to the right of the pivot.
And they will all be passed to a common recursive call.
The second recursive call.
If the pivot is chosen to be bigger than all of these elements,
then they'll all show up on the left side of the partitioned array.
And they'll all be passed to the first recursive call.
Iterating this or proceeding inductively, We see that as long as the pivot is
not drawn from the set of j minus i plus 1 elements.
This entire set will get passed on to the same recursive call.