a pure python implementation of the insertion sort algorithm this algorithm sorts a collection by comparing adjacent elements when it finds that order is not respected it moves the element compared backward until the order is correct it then goes back directly to the element s initial position resuming forward comparison for doctests run following command python3 m doctest v insertionsort py for manual testing run python3 insertionsort py a pure python implementation of the insertion sort algorithm param collection some mutable ordered collection with heterogeneous comparable items inside return the same collection ordered by ascending examples insertionsort0 5 3 2 2 0 2 2 3 5 insertionsort sorted true insertionsort2 5 45 sorted2 5 45 true insertionsort d a b e c sorted d a b e c true import random collection random samplerange50 50 100 insertionsortcollection sortedcollection true import string collection random choicesstring asciiletters string digits k100 insertionsortcollection sortedcollection true a pure python implementation of the insertion sort algorithm param collection some mutable ordered collection with heterogeneous comparable items inside return the same collection ordered by ascending examples insertion_sort 0 5 3 2 2 0 2 2 3 5 insertion_sort sorted true insertion_sort 2 5 45 sorted 2 5 45 true insertion_sort d a b e c sorted d a b e c true import random collection random sample range 50 50 100 insertion_sort collection sorted collection true import string collection random choices string ascii_letters string digits k 100 insertion_sort collection sorted collection true
from collections.abc import MutableSequence
from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
    def __lt__(self, other: Any, /) -> bool:
        ...


T = TypeVar("T", bound=Comparable)


def insertion_sort(collection: MutableSequence[T]) -> MutableSequence[T]:
    

    for insert_index in range(1, len(collection)):
        insert_value = collection[insert_index]
        while insert_index > 0 and insert_value < collection[insert_index - 1]:
            collection[insert_index] = collection[insert_index - 1]
            insert_index -= 1
        collection[insert_index] = insert_value
    return collection


if __name__ == "__main__":
    from doctest import testmod

    testmod()

    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(f"{insertion_sort(unsorted) = }")