# Title: Insertion sort
# Heading: Python Program for Insertion Sort
# Level: beginner
# Tags: sorting, insertion sort, shift, list
# Time: O(n²)
# Space: O(1)
# About: Sorts a list by taking each item in turn and inserting it into its place among the sorted items before it.

def insertion_sort(items):
    """Sort items in place, from smallest to largest."""
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        # Move each bigger item one place right to make room
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = current


numbers = [38, 27, 43, 3, 9, 82, 10]
print("Before:", numbers)
insertion_sort(numbers)
print("After: ", numbers)