Given a list of numbers L, a value x is said to be a majority value if the value of over half the elements in L is x; in other words, if L has n elements and nx is the number of elements in L with value x, then x is a majority element if nx > n=2.
Give a recursive, O(n log n)-time algorithm that determines whether a list L has a majority element, and if so, returns the value of the majority element.