def send_to_goulag(input_list:list)-> list :
    """Sorts a list of numbers using the unique "Goulag Sort" method.

    This algorithm processes a list of numbers through a distinctive iterative and
    recursive procedure, inspired by the "Stalin Sort" concept. Here's how it operates:

    1.  **Iterative Filtering:** It iterates through the main list. If an element
        is found to be greater than its subsequent element, the subsequent element
        is moved to a temporary holding list (`temp`). The main list then continues
        with the remaining elements.

    2.  **Recursive Processing of Held Items:** If the `temp` list contains more than
        one item, the `send_to_goulag` algorithm recursively processes `temp`. This
        filtering and holding process continues until the sub-list contains a single
        item or becomes empty.

    3.  **Partial Re-insertion:** After the recursive calls (or if `temp` was empty/single-item),
        the algorithm attempts to re-insert the elements from `temp` back into the main list.
        This re-insertion is performed by finding a suitable position where the held item
        is less than the current element in the main list, maintaining a partial order.

    4.  **Final Appending:** Any remaining elements in `temp` that were not re-inserted
        into the middle of the list are then appended to the end of the main list.

    For a more detailed step-by-step explanation of the algorithm's flow, please refer to:
    :ref:`goulag_sort_detailed_explanation`.

    Args:
        input_list (list): The list of numbers to be processed and sorted.
                           This list will be modified **in-place**.

    Returns:
        list: The list after being processed by the Goulag Sort algorithm. The result
              is an ordered list.

    Examples:
        >>> from goulag_sort import send_to_goulag
        >>> my_list = [5, 2, 8, 1, 9, 4]
        >>> send_to_goulag(my_list)
        [1, 2, 4, 5, 8, 9]

        >>> empty_list = []
        >>> send_to_goulag(empty_list)
        []
    """


    idx = 0
    temp = []
    is_sorted = True
    while True:

        if not input_list:
            return []

        if len(input_list)<=1:
            return input_list



        while idx < len(input_list) - 1:
            if input_list[idx] > input_list[idx + 1]:
                temp.append(input_list[idx + 1])
                # pop(idx+1) é uma operação O(N) no pior caso
                input_list.pop(idx + 1)
            else:
                idx += 1

        # Chamada recursiva (pode adicionar complexidade se for muito frequente)
        if len(temp) > 1:
            temp = send_to_goulag(temp)

        idx = 0
        # Loop para reinserir elementos de 'temp' na lista principal
        merge_two_sorted_lists_in_place(input_list,temp)

        if temp:
            input_list.extend(temp)  # extend é O(k) onde k é o tamanho de temp
            temp.clear()

        for i in range(len(input_list) - 1):
            if input_list[i] > input_list[i + 1]:
                is_sorted = False
                break
        if is_sorted:
            return input_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