void insertionSort2(int n, vector<int> arr) {
    for (int i = 1; i < n; i++) {
        int current = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
        for(int i = 0; i < n; i++) cout << arr[i] << " ";
        cout << endl;
    }
}

def insertionSort2(n, arr):
    # Write your code here
    for i in range(len(arr)):
        part_sorted = sorted(arr[:(i+1)]) + arr[i+1:]
        if i > 0:
            print(' '.join([str(x) for x in part_sorted]))

public static void insertionSort2(int n, List<Integer> arr) {
        if(n == 1) System.out.println(arr.get(0)); //len of 1 is already sorted
        
        //separate arr into sorted and unsorted portions
        for(int i = 1; i < arr.size(); i++){
            int j = i - 1;
            int currVal = arr.get(i);
            int prevVal = arr.get(j);
            
            //compare prev element with curr element
            if(currVal < prevVal){
                while(currVal < prevVal){
                    arr.set(j + 1, prevVal);
                    arr.set(j, currVal);
                    j--;
                    if(j >= 0) prevVal = arr.get(j);
                    else break;
                }
            }
            
            //print the arr
            arr.forEach(l -> System.out.print(l + " "));
            System.out.println();
        }
    }

def print_array(arr):
    print(' '.join(map(str, arr)))

def insertionSort2(n, arr):
    for i in range(1, n):
        for j in range(i):
            if arr[j] > arr[i]:
                arr[i], arr[j] = arr[j], arr[i]
        print_array(arr)

def insertionSort1(n, arr):
    insert = arr[-1]
    index = list(reversed([i for i in range(len(arr) - 1)]))
    for i in index:
        if insert <= arr[i]:
            arr[i + 1] = arr[i]
        else:
            arr[i + 1] = insert
            return arr
    arr[0] = insert
    return arr

def insertionSort2(n, arr):
    for i in range(2, len(arr) + 1):
        print(" ".join([str (i) for i in insertionSort1(len(arr[:i]), arr[:i]) + arr[i:]]))
        arr = insertionSort1(len(arr[:i]), arr[:i]) + arr[i:]