insertion_sort.py

def insertion_sort(data_list):
    """
    Sorts a list using the Insertion Sort algorithm by shifting and inserting elements.
    """
    # Start from the second element (index 1) as the first is considered sorted
    for i in range(1, len(data_list)):
        key = data_list[i]  # Current element to be positioned
        j = i - 1

        # Shift elements of the sorted portion that are larger than the key
        while j >= 0 and key < data_list[j]:
            data_list[j + 1] = data_list[j]
            j -= 1

        # Place the key in its correct sorted position
        data_list[j + 1] = key

# Testing the implementation
if __name__ == "__main__":
    test_list = [44, 55, 12, 42, 94, 18, 6, 67]
    print(f"Original list (Insertion): {test_list}")
    insertion_sort(test_list)
    print(f"Sorted list   (Insertion): {test_list}")