Insertion Sort¶

1  for j = 2 to A.length
2      key = A[j]
3      // Insert A[j] into the sorted sequence A[1..j-1]
4      i = j -1 
5      while i > 0 and A[i] > key
6          A[i+1] = A[i]
7          i = i - 1
8      A[i+1] = key

def insertion_sort(A):
    """Sorts the array `A` in ascending order using `Insertion sort` algorithm

    Args:
        A: Array of numbers to be sorted

    Returns:
        Array of numbers in sorted, ascending order
    """
    for j in range(1, len(A)):
        key = A[j]
        # Insert A[j] into the sorted sequence A[0..j-1]
        i = j - 1
        while i > -1 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key 
    return A

tests = [
    [31, 41, 59, 26, 41, 58],
    [],
    [40, 20],
    [1],
    [10, 9, 8, 7],
    [7, 8, 9, 10]
]

for input_array in tests:
    print(f'Input: {input_array}')
    output_array = insertion_sort(input_array)
    print(f'Sorted: {output_array}\n')

Input: [31, 41, 59, 26, 41, 58]
Sorted: [26, 31, 41, 41, 58, 59]

Input: []
Sorted: []

Input: [40, 20]
Sorted: [20, 40]

Input: [1]
Sorted: [1]

Input: [10, 9, 8, 7]
Sorted: [7, 8, 9, 10]

Input: [7, 8, 9, 10]
Sorted: [7, 8, 9, 10]