DSA Insertion Sort

How Insertion Sort Works

Insertion sort walks through the list from left to right, treating the first element as a trivially sorted sublist of size one. For each new element, it shifts larger elements in the sorted portion one position to the right and inserts the new element into the gap left behind. This mirrors how many people sort a hand of playing cards.

• Start with the second element as the current key.
• Compare the key against elements to its left in the sorted portion.
• Shift each larger element one position to the right.
• Insert the key into the empty slot.
• Repeat for every remaining element until the list is fully sorted.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

numbers = [9, 5, 1, 4, 3]
print(insertion_sort(numbers))

Tracing Through an Example

Watching the array after each outer loop iteration makes the shifting behavior concrete. Notice how the sorted region on the left grows by exactly one element every pass, while everything to its right remains untouched until its turn comes.

def insertion_sort_verbose(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
        print(f'After step {i}: {arr}')
    return arr

insertion_sort_verbose([9, 5, 1, 4, 3])

Complexity Analysis

def insertion_sort_desc(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] < key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort_desc([3, 7, 2, 9, 1]))