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