Design an algorithm that solves the majority element problem in O$($n log n$)$ time.

The input to your algorithm is a list A$[1...$ n$]$ and the output is the majority element of A$,$if it exists. If there is no majority element, the algorithm should return nil. Present your algorithm in pseudocode and Present an analysis of the runtime of your algorithm, showing that it indeed runs in O$($n log n$).$ An array $\backslash ($ A$[1\backslash$ldots n$]\backslash )$ is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so$,$ to find that element. The tricky part is that the elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form $"$is $\backslash ($ A$[$i$]>$A$[$j$]\backslash )?".$ That also means that you can not sort the elements in any specific order. $($Think of the array elements as GIF files, say.$)$ However you can answer questions of the form: $"$is $\backslash ($ A$[$i$]=$A$[$j$]\backslash )?"$ in constant time.