import java.util.ArrayList;

public class InsertionSort {

    // Inserts a number into a sorted array
    // Precondition: list != null
    // Precondition: list is sorted from small to big
    // Postcondition: list is still sorted
    // Postcondition: x has been inserted into the list
    public static void insert(ArrayList<Integer> list, int x) {

        int pos = 0;
        while ( pos < list.size() && list.get(pos) < x ) {
            pos++;
        }
        list.add(pos, x);

    }

    // Sorts the given list of numbers from small to big
    // Precondition: list != null
    // Postcondition: list is sorted
    public static void insertionSort(ArrayList<Integer> list) {

        ArrayList<Integer> copy = new ArrayList<Integer>();
        for (int i : list) {
            copy.add(i);
        }

        list.clear();

        for (int i : copy) {
            insert(list, i);
        }

    }

}