import javax.swing.*;
import java.awt.*;
import java.util.*;
public class RecMergeSort extends JApplet{

int maxSize = 100;
   private int[] theArray;          // ref to array theArray
   private int nElems=0;               // number of data items

   //-----------------------------------------------------------
   public void insert(int a[],int value)    // put element into array
      {
      a[nElems] = value;      // insert it
      nElems++;                      // increment size
      }
   //-----------------------------------------------------------
   public String display()             // displays array contents
      {String val="";
      for(int j=0; j<nElems; j++)    // for each element,
         val=val+theArray[j] + " ";
     return val;
      }
   //-----------------------------------------------------------
   public void mergeSort()           // called by main()
      {                              // provides workspace
      int[] workSpace = new int[nElems];
      recMergeSort(workSpace, 0, nElems-1);
      }
   //-----------------------------------------------------------
   private void recMergeSort(int[] workSpace, int lowerBound,
                                               int upperBound)
      {
      if(lowerBound == upperBound)            // if range is 1,
         return;                              // no use sorting
      else
         {                                    // find midpoint
         int mid = (lowerBound+upperBound) / 2;
                                              // sort low half
         recMergeSort(workSpace, lowerBound, mid);
                                              // sort high half
         recMergeSort(workSpace, mid+1, upperBound);
                                              // merge them
         merge(workSpace, lowerBound, mid+1, upperBound);
         }  // end else
      }  // end recMergeSort()
   //-----------------------------------------------------------
   private void merge(int[] workSpace, int lowPtr,
                           int highPtr, int upperBound)
      {
      int j = 0;                             // workspace index
      int lowerBound = lowPtr;
      int mid = highPtr-1;
      int n = upperBound-lowerBound+1;       // # of items

      while(lowPtr <= mid && highPtr <= upperBound)
         if( theArray[lowPtr] < theArray[highPtr] )
            workSpace[j++] = theArray[lowPtr++];
         else
            workSpace[j++] = theArray[highPtr++];

      while(lowPtr <= mid)
         workSpace[j++] = theArray[lowPtr++];

      while(highPtr <= upperBound)
         workSpace[j++] = theArray[highPtr++];

      for(j=0; j<n; j++)
         theArray[lowerBound+j] = workSpace[j];
      }  // end merge()
   //-----------------------------------------------------------

public void init()

      {
    Container c=getContentPane();
    c.setLayout(new BorderLayout());
    JTextArea jt=new JTextArea(20,80);
    c.add(jt,BorderLayout.CENTER);
 

                  // array size
                        // reference to array
      theArray = new int[maxSize];     // create the array
Random r=new Random();
     for(int i=0;i<20;i++){
        int v=r.nextInt(10000);
        insert(theArray,v);}

      String s=display();                 // display items

      mergeSort();               // merge sort the array

      String t=display();                 // display items again
      jt.setText("original array=\n");
      jt.append(s+'\n');
     jt.append("sorted"+'\n');jt.append(t+'\n');
      }  // end init()
   }  // end class MergeSortApp
///////////////