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=a=...=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$.