/* <h1>Source code for Nevalainen, Raita &amp; Thimbleby paper, 2002</h1>
   See <a href="http://www.uclic.ucl.ac.uk/harold/warp"><!--
   -->www.uclic.ucl.ac.uk/harold/warp</a> for more details.
   <pre> */

/** 
 * @author Harold Thimbleby, h.thimbleby@ucl.ac.uk
 * @version 1
 */

import java.lang.Comparable;

class InsertSort
{	final static int STABLE = 1, UNSTABLE = 2;

	public static void sort(Comparable a[], int sortType)
	{	// <warp file='identify.tex'>
		int sentinel_position = 0;
		Comparable sentinel_value = a[sentinel_position];
		for( int i = 1; i < a.length; i++ )
			if( a[i].compareTo(sentinel_value) < 0 ) 
				sentinel_value = a[sentinel_position = i];
		// </warp>
		
		if( sortType == UNSTABLE )
		{	// <warp file='unstableinsert.tex'>
				// unstable sort
				a[sentinel_position] = a[0]; 
				a[0] = sentinel_value;
			// </warp>
		}
		else
		{	// <warp file='stableinsert.tex'>
				// stable sort
				for( int i = sentinel_position; i > 0; i-- ) 
					a[i] = a[i-1];
				a[0] = sentinel_value;
			// </warp>
		}
		
		// <warp file='sort.tex'>
		for( int i = 2; i < a.length; i++ )
		{	int j = i;
			Comparable v = a[j];
			while( a[j-1].compareTo(v) > 0 ) 
			{	a[j] = a[j-1];
				j--;
			}
			a[j] = v;
		}
		// </warp>
	}
} // </pre>