import java.util.Comparator;

    
/** Sortieren eines Arrays nach dem Algorithmus Merge-Sort
 */
public class MergeSort
{

    /** mischt zwei benachbarte bereits sortierte Teilbereiche des Arrays
     * @param daten das zu sortierende Array 
     * @param links linker Rand des Teilbereichs
     * @param mitte Mittelpunkt zwischen den Teilbereichen 
     * @param rechts rechter Rand des Teilbereichs 
     * @param vgl das Vergleicherobjekt
     * Vorbedingung:  links <= mitte < rechts 
     *                daten[links..mitte] und daten[mitte+1..rechts] sind sortiert
     * Nachbedingung: daten[links..rechts] ist sortiert 
     */
    public static void mischen(  Object[] daten, int links, int mitte, int rechts, Comparator vgl )
    {
	Object[] kopie = new Object[ rechts - links + 1 ] ;
	int linksAkt = links ; 
	int rechtsAkt = mitte + 1 ; 
	for ( int i = 0 ; i < kopie.length ; i++ ) 
	    { 
		if ( linksAkt <= mitte && ( rechtsAkt > rechts || vgl.compare( daten[linksAkt] , daten[rechtsAkt] ) <= 0 )  ) 
		    { 
			kopie[i] = daten[linksAkt] ;
			linksAkt++ ; 
		    }
		else 
		    {
			kopie[i] = daten[rechtsAkt] ;
			rechtsAkt++ ; 
		    }
	    }
	System.arraycopy( kopie , 0 , daten , links , kopie.length ) ;
    }


    /** sortiert einen Teilbereich eines Arrays nach einem vorgegebenen Vergleich.
     * @param daten das zu sortierende Array 
     * @param links linker Rand des Teilbereichs
     * @param rechts rechter Rand des Teilbereichs 
     * @param vgl das Vergleicherobjekt
     * Vorbedingung: links <= rechts 
     */
    public static void sortieren( Object[] daten, int links, int rechts, Comparator vgl )
    {
	if ( links < rechts )
	    {
		int mitte = ( links + rechts ) / 2 ; 
		sortieren( daten, links , mitte, vgl ) ;
		sortieren( daten, mitte + 1 , rechts, vgl ) ;
		mischen( daten, links , mitte , rechts, vgl ) ; 
	    } 
    }


    /** sortiert ein Array
     * @param daten das zu sortierende Array 
     * @param vgl das Vergleicherobjekt
     */
    public static void sortieren( Object[] daten, Comparator vgl )
    {
	sortieren( daten, 0 , daten.length - 1 , vgl ) ;
    }


}