# -*- coding: utf-8 -*-


def merge(arr, aux, low, high):
    half = (low + high) // 2
    i1, i2, j = low, half + 1, low

    while i1 <= half and i2 <= high:
        if arr[i1] < arr[i2]:
            aux[j] = arr[i1]
            i1 += 1
        else:
            aux[j] = arr[i2]
            i2 += 1

        j += 1

    while i1 <= half:
        aux[j] = arr[i1]
        i1 += 1
        j += 1

    while i2 <= high:
        aux[j] = arr[i2]
        i2 += 1
        j += 1


def merge_sort_r(arr, aux, low, high, swap=True):
    if low >= high:
        return None

    half = (low + high) // 2

    merge_sort_r(arr, aux, low, half, not swap)
    merge_sort_r(arr, aux, half + 1, high, not swap)

    merge(
        aux if swap else arr,
        arr if swap else aux,
        low,
        high
    )


def merge_sort(arr):
    length = len(arr)
    if length <= 1:
        return None

    merge_sort_r(arr, arr[:], 0, length - 1)


#############
# HEAP SORT #
#############
# TASK 0: Finish heap_sort() implementation
# TASK 1: Improve range in heapify()
# TASK 2: Get rid of assumption of array being indexed from 1
# TASK 3: Currently sorting in decreasing order, make this sort in increasing order (hard-code or add direction param)
def heapify_sub(arr, n, root):
    should_be_root = root
    l = 2 * root
    r = 2 * root + 1

    # No left child ==> no right child either ==> nothing to do
    if l >= n:
        return None

    # Left child is "more correct" root
    if arr[root] > arr[l]:
        should_be_root = l

    # Right child exists and is even better than original root or left child
    if r < n and arr[should_be_root] > arr[r]:
        should_be_root = r

    if should_be_root != root:
        # print("swapping %d <--> %d | (%d <--> %d)" % (should_be_root, root, arr[should_be_root], arr[root]))
        arr[root], arr[should_be_root] = arr[should_be_root], arr[root]

        # Heapify the root
        heapify_sub(arr, n, should_be_root)


def heapify(arr):
    arr.insert(0, 0)  # TASK 2: get rid of kung-fu
    n = len(arr)

    # TASK 1: improve range
    for i in range(n, 0, -1):
        heapify_sub(arr, n, i)

    arr.pop(0)  # TASK 2: get rid of this kung-fu


def heap_sort(arr):
    heapify(arr)

    raise NotImplementedError


arrs = [
    [1, 8, 7, 3, 6, 12, 4],
    [1, 8, 7, 3, 6, 12, 4, 22, 15, -2],
]
for array in arrs:
    pass