Sorting array with two elements - in place and minimal number of comparisons, lower bound
$n-1$ comparisons are necessary and sufficient. To show that $n-1$ comparisons are necessary, we consider an adversary that always answers "EQUAL". Suppose that an algorithm makes at most $n-2$ comparisons. Construct a comparison graph whose vertices are the array elements and whose edges are the comparisons. Since the graph has at most $n-2$ edges, it is not connected. Let $C_1,C_2$ be two connected components. It is consistent that the value of all elements in $C_1$ is $0$ and that the value of all elements in $C_2$ is $1$. It is also consistent that all elements in $C_1$ are $1$ whereas all elements in $C_2$ are $0$. No monotone ordering of the array is consistent with both options, showing that the algorithm is incorrect.

To show that $n-1$ comparisons are sufficient, consider the algorithm that compares the first element to all other elements. There are three cases to consider:


The first element is equal to all other elements. In this case the array is already sorted.
The first element equals the elements in $S$ and is smaller than the elements in $T$. Thus the first element and the elements in $S$ have the value $0$ and the elements in $T$ have the value $1$, and we can sort the array accordingly.
The first element equals the elements in $S$ and is larger than the elements in $T$. This is symmetric to the previous case.