Here's a question about using a divide and conquer approach to find a majority element in an array. It's taken from Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Question 2.23. I'm not convinced why this algorithm should work.
It seems to give no direction on what to do with the element that is left unpaired when the array size is odd. Take for example $A = [1, 1, 1, 2, 3]$.
Suppose we keep that unpaired singleton element at each step. For example, if we pair them up as $[1, 1], [1, 2], $, then after keeping $1$, discarding $1, 2$, and keeping $3$, we're left with $1, 3$. Then we discard both since they're different, so we're left with no majority element.
Suppose we don't keep that unpaired singleton at each step. If we pair them up as $[1, 2], [1, 3], $, then we must discard all of them, so again we're left with no majority element.
Where is the flaw? Can someone clarify whether this algorithm keeps or discards the unpaired singleton?