def insettion_sort(arr):
    """
    time complexity: O(n^2)
    space complexity: O(1)
    :prarm arr: list
    :return: list
    """
    if not isinstance(arr, list):
        raise TypeError
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr