Let A(1..n] be an array. A is said to have a majority element if more than half of its elements are the same. Given an array Aj1.n], the task is to design an efficient algorithm to tell whether the has a majority element, and if so, to find that element. The elements of the array are not necessarily from some ordered domain (like the integers), and hence there can be no comparison of the form "is A[i] > A[j]" or "is A[i]

Give an O(nlgn)-time divide-and-conquer algorithm for the above problem/task. (Hint. Split the array A into two subarrays of half the size. Does knowing the majority elements of the two subarrays help figuring out the majority element for A?)