Python insertion sort
Insertion sort maintains a sorted prefix to the left of the current position. Save the current value as key, shift larger prefix values right, then fill the gap.
Python
def insertion_sort(values):
result = values.copy()
for i in range(1, len(result)):
key = result[i]
j = i - 1
while j >= 0 and result[j] > key:
result[j + 1] = result[j]
j -= 1
result[j + 1] = key
return result
print(insertion_sort([3, 1, 2]))
assert insertion_sort([]) == []
assert insertion_sort([2, 2, 1]) == [1, 2, 2]