4.25

In quicksort two distinct elements are only compared when one of them is chosen as the pivot during a partition step. Each element is scanned exactly once in that partition, the pivot is then placed in its final position, and the two resulting sub-arrays are processed independently—so the pair can never meet again. Hence any pair [math]z_i[/math] and [math]z_j[/math] can be directly compared at most one time during the entire execution of quicksort.

Back to Chapter 4