// InsertionSort.java -- insertion sort demo for cs 20
// cmc, 5/26/05

/** Implements and tests an insertion sort for integers. */
public class InsertionSort extends IntSorter {

    /**
       Insertion sort for integer array.
       @param a the array
    */
    public void sort(int a[]) {
        int i, j, key;
        boolean more;

        for (i=1; i<a.length; i++) {
            key = a[i]; // copy the element to be inserted
            j = i;
            more = a[j-1] > key;

            while(more) {
                a[j] = a[j-1]; // move a[j-1] one space right
                j--;
                more = (j > 0) ? (a[j-1] > key) : false;
            }
            a[j] = key;

            print(a); // show intermediate result
        }
    }
}