// Class encapsulating the recursive insertion sort algorithm.
class RecInsertionSort implements SortAlgorithm {
    
    public RecInsertionSort() {
        
    }
    
    // POST: sort the array
    public void sort( int[] array ) {
        iSort( array );
    }
    
    /*
     * POST: array is sorted into non-decreasing order 
     */
    private void iSort(int[] array) {
        recursiveInsertionSort(array, array.length-1);
    }
    
    /*
     * PRE: lastIndex must be valid index for array
     * POST: The elements originally in array[0..lastIndex] have been
     *       rearranged to be in non-decreasing order.
     */
    private void recursiveInsertionSort(int[] array, int lastIndex) {
        if (lastIndex >= 1) { // 2 or more elements
            // sort everything in the array up to lastIndex
            recursiveInsertionSort(array, lastIndex - 1);
            
            // insert element at lastIndex into array[0..lastIndex-1]
            insertNext(lastIndex, array);
        }
    }
    
    /* PRE: array[0..lastIndex-1] is in non-decreasing order and 
     *      lastIndex < array.length, 
     * POST: array[0..lastindex] contains the same elements as it did before
     *       the execution of the method, but now is in non-decreasing order.
     */
    private void insertNext(int lastIndex, int[] array) {
        // Find where array[lastIndex] belongs in final sorted array
        int position = lastIndex-1;		// index where element should be inserted
        
        // Search for first elt (from rear) <=  array[lastIndex]
        while (position >= 0 && array[lastIndex] < array[position]) {
            position--;
        }
        position++;    // position is now where array[lastIndex] belongs
        
        // move array[position .. lastIndex-1] to make room for array[lastIndex]
        // in array[position]
        int tempElt = array[lastIndex];
        for (int moveIndex = lastIndex-1; moveIndex >= position; moveIndex--) {
            array[moveIndex+1] = array[moveIndex];
        }
        // insert element into proper position
        array[position] = tempElt;
        // now array[0..lastIndex] are in order
    }
    
    
    // POST: return the name of this class
    public String toString( ) {
        return "Recursive Insertion Sort";
    }
    
}