Source code for Nevalainen, Raita & Thimbleby paper, 2002
   See www.uclic.ucl.ac.uk/harold/warp for more details.
   
 

/** 
 * @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)
	{			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];
				
		if( sortType == UNSTABLE )
		{					// unstable sort
				a[sentinel_position] = a[0]; 
				a[0] = sentinel_value;
					}
		else
		{					// stable sort
				for( int i = sentinel_position; i > 0; i-- ) 
					a[i] = a[i-1];
				a[0] = sentinel_value;
					}
		
				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;
		}
			}
} 

Simple test harness for InsertSort
   
 
import java.io.*;

class Test
{	public static void main(String args[])
	{	System.out.println("// <save file='output.html'><pre><!-- for whole file translation to XHTML-->");
		for( int type = 1; type <= 2; type++ )
		{	int v[] = { 2, 9, 3, 4, 1, 5, 8, 1, 4, 8, 7, 6 };
			Integer test[] = IntegerVector(v);
			System.out.println("// <save file='sortoutput.tex'>\n"
				+(type==InsertSort.UNSTABLE? "Unstable sort": "Stable sort")
				+"\n    Before sorting "+tostring(test));
			InsertSort.sort((Comparable[]) test, type);
			System.out.println("    After sorting  "+tostring(test)+"\n// </save>");
		}
		System.out.println("// </pre></save>");
	}
	
	static Integer[] IntegerVector(int [] t)
	{	Integer i[] = new Integer[t.length];
		for( int j = 0; j < t.length; j++ )
			i[j] = new Integer(t[j]);
		return i;
	}
	
	static String tostring(Integer a[])
	{	String s = "";
		for( int i = 0; i < a.length; s += a[i++])
			if( i > 0 ) s += ", ";
		return "["+s+"]";
	}
}