def send_to_goulag(main_list: list) -> list:
    if not main_list:
        return [] # Se a lista de entrada está vazia, retorna vazio

    # Se a lista tem 1 ou 0 elementos, ela já está ordenada
    if len(main_list) <= 1:
        return main_list

    filtered_list = []
    gulag_list = []

    # O primeiro elemento sempre vai para a filtered_list como ponto de partida
    filtered_list.append(main_list[0])

    # Percorre o restante da lista original (a partir do segundo elemento)
    # com um único ponteiro 'i'
    for i in range(1, len(main_list)):
        current_item = main_list[i]
        last_in_filtered = filtered_list[-1] # Pega o último item já colocado na filtered_list

        if current_item >= last_in_filtered:
            # Se o item atual mantém a ordem com o que já foi filtrado, adicione-o
            filtered_list.append(current_item)
        else:
            # Se o item atual quebra a ordem, ele é "rejeitado" para o gulag
            gulag_list.append(current_item)

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

    filtered_list = merge_sorted_lists_efficient(filtered_list,gulag_list)

    return filtered_list


def merge_sorted_lists_efficient(list1: list, list2: list) -> list:
    """
    Mescla duas listas ordenadas de forma eficiente, criando uma nova lista resultado.
    Evita as operações custosas de insert/pop no meio das listas.

    Args:
        list1: A primeira lista ordenada.
        list2: A segunda lista ordenada.

    Returns:
        Uma NOVA lista contendo todos os elementos de list1 e list2 mesclados e ordenados.
    """
    merged_list = []
    ptr1 = 0  # Ponteiro para list1
    ptr2 = 0  # Ponteiro para list2

    # Enquanto houver elementos em ambas as listas para comparar
    while ptr1 < len(list1) and ptr2 < len(list2):
        if list1[ptr1] <= list2[ptr2]:  # Note o <= para estabilidade (mantém ordem de iguais)
            merged_list.append(list1[ptr1])
            ptr1 += 1
        else:
            merged_list.append(list2[ptr2])
            ptr2 += 1

    # Adicionar quaisquer elementos restantes de list1 (se houver)
    while ptr1 < len(list1):
        merged_list.append(list1[ptr1])
        ptr1 += 1

    # Adicionar quaisquer elementos restantes de list2 (se houver)
    while ptr2 < len(list2):
        merged_list.append(list2[ptr2])
        ptr2 += 1

    return merged_list