MergeSorter.java Page 1
    1	/** This class sorts an array, using the merge sort algorithm. */
    4	public class MergeSorter
    5	{
    6	   /**
    7	      Constructs a merge sorter.
    8	      @param anArray the array to sort
    9	   */
   10	   public MergeSorter(int[] anArray)
   11	   {
   12	      a = anArray;
   13	   }
   15	   /**
   16	      Sorts the array managed by this merge sorter.
   17	   */
   18	   public void sort()
   19	   {
   20	      if (a.length <= 1) return;
   21	      int[] first = new int[a.length / 2];
   22	      int[] second = new int[a.length - first.length];
   23	      System.arraycopy(a, 0, first, 0, first.length);
   24	      System.arraycopy(a, first.length, second, 0, second.length);
   25	      MergeSorter firstSorter = new MergeSorter(first);
   26	      MergeSorter secondSorter = new MergeSorter(second);
   27	      firstSorter.sort();
   28	      secondSorter.sort();
   29	      merge(first, second);
   30	   }
   32	   /**
   33	      Merges two sorted arrays into the array managed by this
   34	      merge sorter.
   35	      @param first the first sorted array
   36	      @param second the second sorted array
   37	   */
   38	   private void merge(int[] first, int[] second)
   39	   {
   40	      // Merge both halves into the temporary array
   41	
   42	      int iFirst = 0;
   43	         // Next element to consider in the first array
   44	      int iSecond = 0;
   45	         // Next element to consider in the second array
   46	      int j = 0;
   47	         // Next open position in a
   48	
   49	      // As long as neither iFirst nor iSecond past the end, move
   50	      // the smaller element into a
   51	      while (iFirst < first.length && iSecond < second.length)
   52	      {
   53	         if (first[iFirst] < second[iSecond])
   54	         {
   55	            a[j] = first[iFirst];
   56	            iFirst++;
   57	         }
   58	         else
   59	         {
   60	            a[j] = second[iSecond];
   61	            iSecond++;
   62	         }
   63	         j++;
   64	      }
   65	
   66	      // Note that only one of the two calls to arraycopy below
   67	      // copies entries
   68	
   69	      // Copy any remaining entries of the first array
   70	      System.arraycopy(first, iFirst, a, j, first.length - iFirst);
   71	
   72	      // Copy any remaining entries of the second half
   73	      System.arraycopy(second, iSecond, a, j, second.length - iSecond);
   74	   }
   75	
   76	   private int[] a;
   77	}