Insertion Sort

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


# Example usage:
arr = [64, 25, 12, 22, 11]
sorted_arr = insertion_sort(arr)
print("Sorted array:", sorted_arr)
# Sorted array: [11, 12, 22, 25, 64]