Sorting array with two elements - in place and minimal number of comparisons, lower bound Algorithm must be in place.
I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only $1s$ and $0s$.  

Decision tree give us lower bound $\log(n+1)$.  It is to weak, because we know lower bound for findiing minimum, hence our algorithm must do at least $n-1$ comparisons.  If it is lower bound ?  I don't, but I think that it is $n$. 

Why Do I think that lower bound is equal to $n$ ?  

Let consider array $|a|=n$ such that $a[1]=a[2]=...=a[n-1]=0$ and $a[n]=1$.  

It is needed at least $n-2$ comparisons to check that there is $n-1$ equal elements. And additional $2$ comparisons to check that $1$ is greater then rest of elements.  

What is it real lower bound? What about my justification ?  

Edit: We assume model computation as comparison $\le$.
$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.