import java.util.ArrayList;

public class InsertionSort {
    static ArrayList<Integer> insertion_sort(ArrayList<Integer> arr) {

        for (int i=1; i < arr.size(); ++i) {
            // Temp is the VALUE of the element we want to insert
            // into the sorted subarray arr[0..i-1], which is already sorted
            int temp=arr.get(i);
            int red= i - 1;
            while (red >= 0 && arr.get(red) > temp) {
                arr.set(red + 1, arr.get(red));
                red--;
            }
            arr.set(red + 1, temp);
        }

        return arr;
    }
}