a python implementation of the median of medians algorithm to select pivots for quickselect which is efficient for calculating the value that would appear in the index of a list if it would be sorted even if it is not already sorted search in time complexity on at any rank deterministically https en wikipedia orgwikimedianofmedians return the median of the input list param arr array to find median of return median of arr medianoffive2 4 5 7 899 5 medianoffive5 7 899 54 32 32 medianoffive5 4 3 2 4 medianoffive3 5 7 10 2 5 return a pivot to partition data on by calculating median of medians of input data param arr the data to be checked a list return median of medians of input array medianofmedians2 4 5 7 899 54 32 54 medianofmedians5 7 899 54 32 32 medianofmedians5 4 3 2 4 medianofmedians3 5 7 10 2 12 12 two way partition the data into smaller and greater lists in relationship to the pivot param arr the data to be searched a list param target the rank to be searched return element at rank target quickselect2 4 5 7 899 54 32 5 32 quickselect2 4 5 7 899 54 32 1 2 quickselect5 4 3 2 2 3 quickselect3 5 7 10 2 12 3 5 invalid input x is the estimated pivot by median of medians algorithm return the median of the input list param arr array to find median of return median of arr median_of_five 2 4 5 7 899 5 median_of_five 5 7 899 54 32 32 median_of_five 5 4 3 2 4 median_of_five 3 5 7 10 2 5 return a pivot to partition data on by calculating median of medians of input data param arr the data to be checked a list return median of medians of input array median_of_medians 2 4 5 7 899 54 32 54 median_of_medians 5 7 899 54 32 32 median_of_medians 5 4 3 2 4 median_of_medians 3 5 7 10 2 12 12 two way partition the data into smaller and greater lists in relationship to the pivot param arr the data to be searched a list param target the rank to be searched return element at rank target quick_select 2 4 5 7 899 54 32 5 32 quick_select 2 4 5 7 899 54 32 1 2 quick_select 5 4 3 2 2 3 quick_select 3 5 7 10 2 12 3 5 invalid input x is the estimated pivot by median of medians algorithm
def median_of_five(arr: list) -> int:
    
    arr = sorted(arr)
    return arr[len(arr) // 2]


def median_of_medians(arr: list) -> int:
    

    if len(arr) <= 5:
        return median_of_five(arr)
    medians = []
    i = 0
    while i < len(arr):
        if (i + 4) <= len(arr):
            medians.append(median_of_five(arr[i:].copy()))
        else:
            medians.append(median_of_five(arr[i : i + 5].copy()))
        i += 5
    return median_of_medians(medians)


def quick_select(arr: list, target: int) -> int:
    

    
    if target > len(arr):
        return -1

    
    x = median_of_medians(arr)
    left = []
    right = []
    check = False
    for i in range(len(arr)):
        if arr[i] < x:
            left.append(arr[i])
        elif arr[i] > x:
            right.append(arr[i])
        elif arr[i] == x and not check:
            check = True
        else:
            right.append(arr[i])
    rank_x = len(left) + 1
    if rank_x == target:
        answer = x
    elif rank_x > target:
        answer = quick_select(left, target)
    elif rank_x < target:
        answer = quick_select(right, target - rank_x)
    return answer


print(median_of_five([5, 4, 3, 2]))