Insertion Sort
code: python
# O(n^2), O(1)
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
for j in range(i, 0, -1):
if arr
j
< arr
j-1
:
arr
j
, arr
j-1
= arr
j-1
, arr
j
return arr
def test_insertion_sort():
assert insertion_sort(
5, 3, 4, 7, 2, 8, 6, 9, 1
) ==
1, 2, 3, 4, 5, 6, 7, 8, 9