Divide and Conquer majority element algorithm

Question

The algorithm should return the majority element if it exists (majority meaning that there are $> n/2$ occurrences in the array)

I came up with this linear divide and conquer algorithm, but I'm not sure if it's correct. It returns an array with two elements, the name of the majority element and a number that is less than or equals to its occurrences. Can someone help to prove/disprove it?

def findMajority(arr):
    if len(arr) == 1:
        return [arr[0], 1]
    else:
        leftHalf = findMajority(arr[:len(arr)/2])
        rightHalf = findMajority(arr[len(arr)/2:])

        if leftHalf[0] is None and rightHalf[0] is not None: #Left half is indeterminate
            return [rightHalf[0], rightHalf[1]]

        if leftHalf[0] is not None and rightHalf[0] is None: #Right half is indeterminate
            return [leftHalf[0], leftHalf[1]]

        if leftHalf[0] is None and rightHalf[0] is None: #Both halves are indeterminate
            return [None, 0]

        if leftHalf[0] == rightHalf[0]: #Majority in both halves is the same
            return [leftHalf[0], leftHalf[1] + rightHalf[1]]

        elif leftHalf[1] < rightHalf[1]: #Right majority has more occurrences
            return [rightHalf[0], rightHalf[1]]

        elif leftHalf[1] > rightHalf[1]: #Left majority has more occurrences
            return [leftHalf[0], leftHalf[1]]

        else: #There is no winner between the two halves and they have equal occurrences
            return [None, 0]

EDIT: It returns the wrong answer for [2,2,2,2,1,1,1,0,1,1,1,0,1,1,1,0] . So it doesn't work.

Answer 1

It's not correct. On input [a a b c], the left side yields [a, 2], the right side yields [nil, 1]. They would be merged into [a, 2].

I'll outline a linear time solution. If there exists a value $x$ such that more than $n/2$ of the elements of $A$ have value $x$, then certainly the $n/2$-th order statistic of $A$ must be $x$. The selection problem is solved in linear time using, for example, median of medians; checking that such value does indeed appear at least $n/2$ times is trivially linear time.