def heapify(array, n, i):

    largest = i  
    left = 2 * i + 1 
    right = 2 * i + 2  

    if left < n and array[left] > array[largest]:
        largest = left

    if right < n and array[right] > array[largest]:
        largest = right

    if largest != i:
        array[i], array[largest] = array[largest], array[i]  
        heapify(array, n, largest)

def heap_sort(array):
    n = len(array)

    # Construire un tas max
    for i in range(n // 2 - 1, -1, -1):
        heapify(array, n, i)

    
    for i in range(n - 1, 0, -1):
        array[i], array[0] = array[0], array[i]  
        heapify(array, i, 0)  

    return array

def total_sum(array):
    if isinstance(array[0], int):  
        return sum(array)
    return sum(total_sum(subarray) for subarray in array)  # Si tableau multidimensionnel


def sort_with_sum(array):
    for i in range(1, len(array)):
        key = array[i]
        key_sum = total_sum(key)
        j = i - 1
        # Réorganise les sous-tableaux en fonction de leur somme
        while j >= 0 and total_sum(array[j]) > key_sum:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key
        
    return  array
    


def sort_nd_array(array):
    # Si le tableau est de dimension 1, tri simple par insertion
    if isinstance(array[0], int):
        return heap_sort(array)

    # Si le tableau est multidimensionnel, on trie récursivement les sous-tableaux
    sorted_subarrays = [sort_nd_array(subarray) for subarray in array]

    sorted_subarrays = sort_with_sum(sorted_subarrays)

    return sorted_subarrays


def print_nd_array(array, level=0):
    """
    Affiche un tableau N-dimensionnel de manière lisible.
    """
    if isinstance(array[0], int):  # Si tableau 1D  
        print("  " * level + str(array))
    else:  # Tableau multidimensionnel
        print("  " * level + "[")
        for subarray in array:
            print_nd_array(subarray, level + 1)
        print("  " * level + "]")


def main():
    # Exemple 1 : Tableau 2D
    array_2d = [[0, 3, 2], [9, 4, 5], [4, 1, 3]]
    print("Tableau 2D avant tri :")
    print_nd_array(array_2d)
    result_2d = sort_nd_array(array_2d)
    print("Tableau 2D après tri :")
    print_nd_array(result_2d)

    # Exemple 2 : Tableau 3D
    array_3d = [
        [[3, 1], [4, 2], [1, 3]],
        [[5, 7], [2, 8], [9, 4]],
        [[0, 0], [1, 1], [1, 0]]
    ]
    print("\nTableau 3D avant tri :")
    print_nd_array(array_3d)
    result_3d = sort_nd_array(array_3d)
    print("Tableau 3D après tri :")
    print_nd_array(result_3d)

    # Exemple 3 : Tableau 4D
    array_4d = [
        [
            [[1, 3], [4, 5], [2, 2]],
            [[7, 8], [5, 6], [3, 4]]
        ],
        [
            [[9, 1], [6, 7], [8, 3]],
            [[2, 5], [7, 3], [9, 9]]
        ],
        [
            [[3, 3], [2, 1], [5, 6]],
            [[4, 2], [8, 7], [3, 9]]
        ]
    ]
    print("\nTableau 4D avant tri :")
    print_nd_array(array_4d)
    result_4d = sort_nd_array(array_4d)
    print("Tableau 4D après tri :")
    print_nd_array(result_4d)
    
if __name__ == "__main__":
    main()