class MergesortDemo
{ final int MAXINDEX=200000-1;
  int[] feld;
  int[] ablage;
  Stoppuhr t;
   
  public MergesortDemo()
  { feld = new int[MAXINDEX+1];
    ablage = new int[MAXINDEX+1]; // Hilfsfeld
    t = new Stoppuhr();
    action();
  }
  
  void feldFuellen()
  { for (int i=0; i<=MAXINDEX; i++)
    {  feld[i] = (int)Math.round(Math.random()*9000.0 + 100); }
  } // feldFuellen

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

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
  boolean richtigSortiert()
  {  for (int i=0; i<MAXINDEX; i++)
           if (feld[i]>feld[i+1]) return false;
     return true;
  }
  
  public void action()
  { System.out.println("Mergesort-Demo: ");
    feldFuellen();  // feldAusgabe();
    t.starte();       mergesort(0, MAXINDEX);      t.stoppe();     // feldAusgabe();
    int anzahl = MAXINDEX+1;
    System.out.println("Zeit: " + t.lies() + " ms fuer " + anzahl + " Elemente.");
    if (richtigSortiert()) System.out.print("OK");
  } // action
} // class MergesortDemo