Values during the sorting operation are selected into sorted locations relative to each other base on pair wise comparisons and that information gained from pair wise comparisons can only be reused from a binary structure which is implicitly or explicitly within the structure of the algorithm.

Consider the set of $N$ values in the set $D$ to be sorted. Assume that $D = {x_0, x_1, cdot x_{N-1}}$ is the original permutation of the set. Define the macro $Compare(x_i, x_j) = (true or false); i \ne j \in {0, 1, 2, \cdots N-1}$. We have that $Compare(x_i, x_j) --> Exchange(x_i, x_j) if Compare(x_i, x_j) = false given that i < j$. The theory assumes that for any known $Compare(x_i, x_j) = true$ this information is obtained only by comparison between $x_i$ and $x_j$ or from information implicitly or explicitly represented in in a binarystructure. This binary structure in some case is created by the algorithm explicitly in memory such as with heap sort or implicitly such as with binary insertion sort. Hence, such structure is often used to construct this proof.