How to prove that algorithm returns the value which appears more than $n/2$ times in the array?
Note: In my opinion, although the answer given by @Sunny Wang is slightly hard to follow, it is in the right direction. Maybe the author would like to come back and improve his/her answer. Therefore, I will only give some high-level hints here.

Playing with some examples, you will find that the program amounts to keeping eliminating (by decreasing the counter, of course) a pair of distinct elements. Therefore, if a value appears more than $\frac{n}{2}$ times, it (and only it; this is also important) survives and will be returned.