Let $A$ be an array of $n$ elements consisting of only $-1,1,0$. What is the least number of comparisons that must be made in worst case to sort the array?
At first I was thinking of the answer is 0 because this can be solved easily with count sort without using any direct comparison between elements. But I think the problem wants to use a Comparison-based sorting algorithm. I don't know what should I do to specifically sort array of three numbers in least comparisons.
On
If we are talking about the minimum amount of comparisons required in a worst case comparison sort, it should be understood that all general comparison sorting algorithms taking $O(n\log n)$ time. Of these algorithms I'm not sure which has the best actual operation count, but in the worst case we can rule out all $O(n^2)$ algorithms, which includes things like quicksort, bubble sort, insertion sort, etc. Leaving us with things like mergesort, heapsort, Timsort, etc.
You will have to do a look into the comparisons of the latter, but I think a good contender is mergesort, as the number of operations is constant with respect to changes in input order.
Assuming we have an array of size $n=2^k$, just so that the divisions can be easier creating an upper bound for us, we can see that since merge sort runs through the two lists to merge until one is complete, each time two lists of size $m$ are merged, there will be precisely $m$ comparison operations. This gives us a total count of merges and operations as
$$ O = \dfrac{n}{2} + 2\dfrac{n}{4} + 4\dfrac{n}{8} + ... + 2^{k-1}\dfrac{n}{2^k}=\sum_{j=1}^k \dfrac{n}{2} = \dfrac{kn}{2} = \dfrac{n\log_2 n}{2} $$
which is the exact number of comparison operations for mergesort of an array of a length that is to the power of $2$. This formula would have to be modified to account for array lengths that aren't as well behaved, however it provides a nice upper bound. Also I have no proof that this is in fact the absolute minima number of operations, but its just one possibility of an algorithm
I think you can do this in $O(n)$. Something like walking through the numbers, counting the number of each element. Then just print out, in order, the appropriate number of $-1$, $0$, and $1$s. Perhaps it depends on how strictly they interpret 'comparison,' but arguably that would take 0 comparisons.
Hmm, I still think $O(n)$. If you use insertion sort, and can simply place all encountered $-1$ at one end of a queue and all $1$ at the other end, at worst that'd be $n$ too. Again, depends on 'comparison' though, though it's fair to say you'd be comparing each element one at a time against $0$.