void printf_arr(int n, int* arr){
    for(int i=0; i<n; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Done inplace
void insertionSort1(int n, int arr_count, int* arr) {
    int right_most_idx = arr_count-1;
    int num = arr[right_most_idx];
    while(num < arr[right_most_idx-1]){
        arr[right_most_idx] = arr[right_most_idx-1];
        printf_arr(n,arr);
        right_most_idx --;
    }
    arr[right_most_idx] = num;
    printf_arr(n, arr);
}