class Solution:
    def majorityElement(self, arr: List[int]) -> int:
        def quick_sort(arr, l, r):
            if l >= r:
                return
            i, j = l, r
            while i < j:
                while i < j and arr[j] >= arr[l]:
                    j -= 1
                while i < j and arr[i] <= arr[l]:
                    i += 1
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            x = arr[l]
            arr[l] = arr[i]
            arr[i] = x
            quick_sort(arr, l, i - 1)
            quick_sort(arr, i + 1, r) 
        quick_sort(arr, 0, len(arr) - 1)
        return arr[len(arr)// 2]