import unittest

# insertion sort implementation
# time complexity: O(n^2)
# space complexity: O(1)
def insertion_sort(arr):
    if not arr or len(arr) <= 1:
        return arr
    for i in range(len(arr)):
        var = arr[i]
        j = i
        while j > 0 and arr[j-1] > var:
            arr[j] = arr[j-1]
            j -= 1
        arr[j] = var
        print("inserting ", var, " at position", j, " in arr ", arr)
    return arr

class Test(unittest.TestCase):

    def test_insertion_sort(self):
        input = [4, 1, 5, 1, 7, 0, 9, 2]
        output = insertion_sort(input)
        expected = [0, 1, 1, 2, 4, 5, 7, 9]
        self.assertEqual(expected, output)

unittest.main(verbosity=2)