Complexity of finding a majority element
Let us denote the running time of your algorithm on arrays of size $n$ by $T(n)$. Then
$$
T(n) = \begin{cases}
T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n), &amp; \text{if } n &gt; 2, \\
O(1), &amp; \text{if } n \leq 2.
\end{cases}
$$
The master theorem now shows that $T(n) = O(n\log n)$.



Here is an $O(n)$ algorithm:

find-majority-element(A):
  n = len(A)
  if n = 0:
    return "none"
  if n is odd:
    y = last element of A
    if y is a majority element:
      return y
    A' = A with last element removed
    x = find-majority-element(A')
    if x is a majority element:
      return x
    otherwise:
      return "none"
  partition A into m = n/2 pairs (a_1,b_1),...,(a_m,b_m)
  construct an array B consisting of all a_i such that a_i = b_i
  x = find-majority-element(B)
  if x is a majority element:
    return x
  otherwise:
    return "none"


Clearly if there is no majority element, the algorithm returns "none". Now suppose that $x$ is a majority element. We will show that the algorithm returns $x$. We will do this by proving the following claim by induction on $n=\mathrm{len}(A)$:


  If $A$ contains a majority element $x$, then find-majority-element($A$) returns $x$.


Suppose first that $n=2m+1$ is odd, so that $x$ appears at least $m+1$ times. If $x$ is the last element, then find-majority-element($A$) will return it. Otherwise, $x$ is a majority element of $A'$ as well, and so find-majority-element($A'$) will return $x$, causing find-majority-element($A$) to return it as well.

We can now assume that $n = 2m$ is even. Suppose that $B$ contains $k$ many $x$'s and $\ell$ many other elements. We can upper-bound the number of copies of $x$ in $A$ by $2k + (n-2k-2\ell)/2 = m + k - \ell$. On the other hand, the number of copies is at least $m+1$, and so $k &gt; \ell$. In other words, $x$ is a majority element in $B$ as well. Therefore find-majority-element($B$) will return $x$, causing `find-majority-element($A$) to return it as well.

Denoting by $T(n)$ the maximum running time of the procedure on arrays of length at most $n$, we get the recurrence
$$
T(n) \leq \begin{cases}
O(1), &amp; \text{if } n = 0, \\
T(n-1) + O(n), &amp; \text{if $n$ is odd}, \\
T(n/2) + O(n), &amp; \text{if $n$ is even},
\end{cases}
$$
whose solution is $T(n) = O(n)$.