// Algorithm: Insertion Sort
// Type: Sorting (Comparison-based)
// Time Complexity: O(n^2)
// Space Complexity: O(1)

function insertionSort(arr):
    for i from 1 to length(arr) - 1:
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key