I honestly thought there were 2 (I need read more carefully). Assuming there are c candidates, you need O(nc) operations in the way I was describing, and, indeed, O(n2 ) if c = n. Let's carry on with the assumption that every single ballon can potentially be unique.
Imagine you enumerate every ballot b0, b1,..., b(n-1) and assume that every one is for a unique candidate until proven otherwise. b0's candidate, by definition, is less than or equal to all the others. b1's, if different, is next in magnitude, and so on. You line up the ballots in order, getting a list like:
b0, b1, b2, b3, ..., b(n-1)
To add to this definition, if you were to somehow find out that b2 and b0 are for the same candidate, you would re-name b2 to b0 and reorder your list like this:
b0, b0, b1, b3, ..., bn
Now, assume you have two already sorted lists, each of size n/2. That is, each of the lists already looks something like
b0, b0, b1, b1, b2, ..., b(n/2-1-k)
b(n/2), b(n/2+1), b(n/2+1), b(n/2+1), b(n/2+2), ..., b(n-1-l)
with k and l unique candidates, respectively. Because there's now a concept of "greater than" and "less than", you can just start merging them. First compare b(n/2) to every element in the first list, in order. If you don't find a match, the correct ordering is simply the concatenation of the lists (optionally with the indices of the latter shifted so that the resultant list goes from b0 to b(n-1-l-k)). If you do find a match, say b(n/2) and b1, then you insert it to get:
b0, b0, b1, b1, b1, b2, ..., b(n/2-1-k)
b(n/2+1), b(n/2+1), b(n/2+1), b(n/2+2), ..., b(n-1-l)
but from that point forward you only have to compare b(n/2+1) with b2 and up (again, because we have defined a way to do a less-than-like comparison). That is, you're doing min(k,l)<=n/2 comparisons only. As a base case, a 2-element sublist is always sorted (by definition) and only needs to be compared for equality. By the exact same rationale as for mergesort, the complexity is O(n log n).