a recursive implementation of the insertion sort algorithm given a collection of numbers and its length sorts the collections in ascending order param collection a mutable collection of comparable elements param n the length of collections col 1 2 1 recinsertionsortcol lencol col 1 1 2 col 2 1 0 1 2 recinsertionsortcol lencol col 2 1 0 1 2 col 1 recinsertionsortcol lencol col 1 checks if the entire collection has been sorted inserts the index1th element into place col 3 2 4 2 insertnextcol 1 col 2 3 4 2 col 3 2 3 insertnextcol 2 col 3 2 3 col insertnextcol 1 col checks order between adjacent elements swaps adjacent elements since they are not in ascending order given a collection of numbers and its length sorts the collections in ascending order param collection a mutable collection of comparable elements param n the length of collections col 1 2 1 rec_insertion_sort col len col col 1 1 2 col 2 1 0 1 2 rec_insertion_sort col len col col 2 1 0 1 2 col 1 rec_insertion_sort col len col col 1 checks if the entire collection has been sorted inserts the index 1 th element into place col 3 2 4 2 insert_next col 1 col 2 3 4 2 col 3 2 3 insert_next col 2 col 3 2 3 col insert_next col 1 col checks order between adjacent elements swaps adjacent elements since they are not in ascending order
from __future__ import annotations


def rec_insertion_sort(collection: list, n: int):
    
    
    if len(collection) <= 1 or n <= 1:
        return

    insert_next(collection, n - 1)
    rec_insertion_sort(collection, n - 1)


def insert_next(collection: list, index: int):
    
    
    if index >= len(collection) or collection[index - 1] <= collection[index]:
        return

    
    collection[index - 1], collection[index] = (
        collection[index],
        collection[index - 1],
    )

    insert_next(collection, index + 1)


if __name__ == "__main__":
    numbers = input("Enter integers separated by spaces: ")
    number_list: list[int] = [int(num) for num in numbers.split()]
    rec_insertion_sort(number_list, len(number_list))
    print(number_list)