/**
  *
  * Programmieraufgabe P-18 (MergeSort.java)
  *
  * @author Leonhard Fellermayr
  * @version 1.1
  *
  */

/** Benoetigtes Package: der Comparator zum Vergleichen von Daten */

import java.util.Comparator;

/** Implementierung der Klasse MergeSort. */

public class MergeSort
{

   /******************************************************************************************
      * sortieren (Object[], Comparator) : Sortiert die Werte im Array (o) gemaess dem
      * uebergebenen Comparator (c) via MergeSort-Algorithmus.
      *
      * @param o Das zu sortierende Array von Objekten
      * @param c Comparator-Objekt, das beim Vergleich zum Einsatz kommt
      * @return void
      *
      **/

    public static void sortieren (Object[] o, Comparator c)
    {

	/** Hat das Array eine Laenge <= 1, so ist eine Sortierung ueberfluessig */

	if (o.length > 1)
	{

	    /** Splitte o (Laenge n) in zwei Teile l := [0..n/2] und r := [n/2+1..n]    */

	    Object[] l = new Object[o.length / 2];
	    Object[] r = new Object[o.length - l.length];

	    /** Fuelle die beiden neuen Arrays l und r mit den Inhalten von o           */

	    System.arraycopy (o, 0,        l, 0, l.length);
	    System.arraycopy (o, l.length, r, 0, r.length);

	    /** Die Intention von MergeSort: gesplittete Teile sortieren, dann mergen   */

	    sortieren (l, c);		/** rek. Aufruf fuer linkes Teilarray           */
	    sortieren (r, c);		/** rek. Aufruf fuer rechtes Teilarray          */
	    mergen (l, r, o, c);	/** Zusammenfuehren im Reissverschlussverfahren */

	}

    } // sortieren ()

   /******************************************************************************************
      * mergen (Object[], Object[], Object[], Comparator) : Fuehrt die Inhalte der ersten
      * beiden Arrays (l, r) im dritten (o) via Reissverschlussverfahren zusammen ("merging").
      * Fuer saemtliche Vergleiche wird dabei das uebergebene Comparator-Objekt (c) eingesetzt.
      *
      * @param l Linkes Quellarray
      * @param r Rechtes Quellarray
      * @param result Zusammengefuehrtes Ergebnis-Array (Zielarray)
      * @param c Comparator-Objekt, das beim Vergleich zum Einsatz kommt
      * @return void
      *
      **/

    private static void mergen (Object[] l, Object[] r, Object[] result, Comparator c)
    {

	/** Benoetigte Zaehlvariablen */

	int i = 0;	/** Gibt die aktuelle Position im linken Quellarray (l) vor      */
	int j = 0;	/** Gibt die aktuelle Position im rechten Quellarray (r) vor     */
	int k = 0;	/** Gibt die aktuelle Position im Zielarray (result) vor         */

	/** Iteriere, solange BEIDE Quellarrays noch nicht am Ende angelangt sind,
	  * sprich: bis eines der Quellarrays am Ende angelangt. */

	while ( (i < l.length) && (j < r.length) )
	{
		/** linker Wert "kleiner" als rechter Wert => linken Wert ins Zielarray  */
		if ( c.compare ( l[i], r[j] ) > 0 )
		{
			result[k] = l[i];
			i++;     /** ein Wert weniger im linken Quellarray zu bearbeiten */
		}
		/** rechter Wert "kleiner" als linker Wert => rechten Wert ins Zielarray */
		else
		{
			result[k] = r[j];
			j++;    /** ein Wert weniger im rechten Quellarray zu bearbeiten */
		}
		k++; /** naechster Index im Zielarray */
	}

	/** Nachdem die beiden Quellarrays nicht zwangslaeufig gleich lang sind
	  * (-> ungerade Anzahl Array-Elemente), ist u. U. in einem der Arrays
	  * ein Element (das groesste) verblieben.
	  * Die nachfolgenden Anweisungen stellen sicher, dass dieser "Rest" auf jeden
	  * Fall auch noch hinten im Zielarray angehaengt wird.
	  */

	System.arraycopy (l, i, result, k, l.length - i);
	System.arraycopy (r, j, result, k, r.length - j);

    } // merge ()

} // Klasse MergeSort