find max and min index of an array with 3/2N comparisons

max_and_min.py

def max_min(arr):
    length = len(arr)
    if length <= 1:
      return 0
    even_length = length
    last = None
    if length % 2 == 1:
        last = arr[length-1]
        even_length -= 1
    i = 0
    max_index_list = []
    min_index_list = []
    max_index_list_length = 0
    min_index_list_length = 0

    while i < (even_length-1):
        if arr[i] <= arr[i+1]:
            min_index_list.append(i)
            max_index_list.append(i+1)
        else:
            min_index_list.append(i+1)
            max_index_list.append(i)
        max_index_list_length += 1
        min_index_list_length += 1
        i += 2
    if last:
        if last < arr[length-2]:
            min_index_list.append(length-1)
            min_index_list_length += 1
        else:
            max_index_list.append(length-1)
            max_index_list_length += 1
    return {
        "max": sub(arr, max_index_list, max_index_list_length, 1),
        "min": sub(arr, min_index_list, min_index_list_length, 0)
    }

def sub(arr, index_list, index_list_length, com):
    if index_list_length == 1:
        return index_list[0]
    even_length = index_list_length
    last = None
    if index_list_length % 2 == 1:
        last = arr[index_list[index_list_length-1]]
        even_length -= 1
    sub_index_list = []
    sub_index_length = 0
    i = 0
    while i < (even_length-1):
        if compare(arr[index_list[i]], arr[index_list[i+1]], com):
            sub_index_list.append(index_list[i])
        else:
            sub_index_list.append(index_list[i+1])
        sub_index_length += 1
        i += 2
    if last:
        if compare(last, arr[index_list[0]], com):
            sub_index_list.append(index_list[index_list_length-1])
            sub_index_length += 1

    return sub(arr, sub_index_list, sub_index_length, com)


def compare(a, b, com):
    if com:
        return a > b
    return a < b