class Mergesort
{ static final int maxIndex=99999;
  static int[] feld = new int[maxIndex+1];
  static int[] ablage = new int[maxIndex+1]; // Hilfsfeld

  static void feldFuellen()
  { for (int i=0; i<=maxIndex; i++)
    {  feld[i] = (int)Math.round(Math.random()*900.0 + 100); }
  } // feldFuellen

  static void feldAusgabe()
  { Out.println("Das Feld enthaelt die folgenden Elemente: ");
    for (int i=0; i<=maxIndex; i++)
    {  Out.print(feld[i]);
       Out.print(" ");
    }
    Out.println();
  } // feldAusgabe

static void mergesort(int links, int rechts)
{ if (rechts > links) // mehr als ein Element
       { // Feld teilen und Teilfelder sortieren
         int mitte = (links + rechts)/2;
         mergesort(links, mitte);
         mergesort(mitte+1, rechts);

         // Hilfsfeld fuellen
         for (int k=links; k<=mitte; k++)    // linken Teil normal kopieren
              ablage[k] = feld[k];
         for (int k=mitte+1; k<=rechts; k++) // rechten Teil umgekehrt kopieren
              ablage[rechts + mitte - k + 1] = feld[k];

         // Aus Ablage zurueck ins urspruengliche Feld mischen
         int nachlinks = rechts; // Laufvariable von rechts nach links
         int nachrechts = links; // Laufvariable von links nach rechts
                                 // Die kleinsten Elemente stehen jeweils
                                 // an den Enden des Hilfsfeldes
         for (int k=links; k<=rechts; k++)
         {  if (ablage[nachrechts] < ablage[nachlinks])
                 { feld[k] = ablage[nachrechts];
                   nachrechts++;
                 }
            else { feld[k] = ablage[nachlinks];
                   nachlinks--;
                 }
         }
       } // end if
}  // mergesort

  public static void main(String[] arg)
  {
    Out.println("Mergesort-Demo: ");
    feldFuellen();
//    feldAusgabe();
    Stoppuhr t = new Stoppuhr();
    t.starte();
    mergesort(0, maxIndex);
    t.stoppe();
//    feldAusgabe();
    Out.println("Zeit: " + t.lies() + " ms.");
  } // main
} // class Mergesort