import copy


def send_to_goulag(main_list:list)->list:
    if not main_list:
        return main_list
    itens_to_be_reinserted = []

    main_list_copy = copy.deepcopy(main_list)
    i = 0
    while i < len(main_list) - 1:
        if main_list[i] > main_list[i+1]:
            itens_to_be_reinserted.append(main_list[i+1])
            main_list.pop(i+1)

        else:
            i += 1

    if not itens_to_be_reinserted and main_list == main_list_copy:
        return main_list



    if len(itens_to_be_reinserted)>1:
        itens_to_be_reinserted = send_to_goulag(itens_to_be_reinserted)

    i = 0

    merge_two_sorted_lists_in_place(main_list,itens_to_be_reinserted)

    main_list = send_to_goulag(main_list)

    return main_list

def merge_two_sorted_lists_in_place(list1: list, list2: list) -> list:

    if not list2:
        return list1
    if not list1:
        list1.extend(list2)
        list2.clear()
        return list1


    ptr1 = 0
    ptr2 = 0


    while ptr1 < len(list1) and ptr2 < len(list2):
        if list1[ptr1] > list2[ptr2]:

            list1.insert(ptr1, list2[ptr2])

            ptr1 += 1

            list2.pop(ptr2)
        else:

            ptr1 += 1


    if list2:
        list1.extend(list2)
        list2.clear() # Esvazia list2

    return list1