1  import java.util.*;
  2  
  3  /**
  4     This class carries out the merge sort algorithm.
  5  */
  6  public class MergeSorter
  7  {
  8     /**
  9        Sorts an array, using the merge sort algorithm.
 10        @param a the array to sort
 11        @param comp the comparator to compare array elements
 12     */
 13     public static <E> void sort(E[] a, Comparator<? super E> comp)
 14     {
 15        mergeSort(a, 0, a.length - 1, comp);
 16     }
 17  
 18     /**
 19        Sorts a range of an array, using the merge sort
 20        algorithm.
 21        @param a the array to sort
 22        @param from the first index of the range to sort
 23        @param to the last index of the range to sort
 24        @param comp the comparator to compare array elements
 25     */
 26     private static <E> void mergeSort(E[] a, int from, int to,
 27        Comparator<? super E> comp)
 28     {
 29        if (from == to) return;
 30        int mid = (from + to) / 2;
 31        // Sort the first and the second half
 32        mergeSort(a, from, mid, comp);
 33        mergeSort(a, mid + 1, to, comp);
 34        merge(a, from, mid, to, comp);
 35     }
 36  
 37     /**
 38        Merges two adjacent subranges of an array
 39        @param a the array with entries to be merged
 40        @param from the index of the first element of the
 41           first range
 42        @param mid the index of the last element of the
 43           first range
 44        @param to the index of the last element of the
 45           second range
 46        @param comp the comparator to compare array elements
 47     */
 48     private static <E> void merge(E[] a,
 49        int from, int mid, int to, Comparator<? super E> comp)
 50     {
 51        int n = to - from + 1;
 52           // Size of the range to be merged
 53  
 54        // Merge both halves into a temporary array b
 55        Object[] b = new Object[n];
 56  
 57        int i1 = from;
 58           // Next element to consider in the first range
 59        int i2 = mid + 1;
 60           // Next element to consider in the second range
 61        int j = 0;
 62           // Next open position in b
 63  
 64        // As long as neither i1 nor i2 past the end, move
 65        // the smaller element into b
 66        while (i1 <= mid && i2 <= to)
 67        {
 68           if (comp.compare(a[i1], a[i2]) < 0)
 69           {
 70              b[j] = a[i1];
 71              i1++;
 72           }
 73           else
 74           {
 75              b[j] = a[i2];
 76              i2++;
 77           }
 78           j++;
 79        }
 80  
 81        // Note that only one of the two while loops
 82        // below is executed
 83  
 84        // Copy any remaining entries of the first half
 85        while (i1 <= mid)
 86        {
 87           b[j] = a[i1];
 88           i1++;
 89           j++;
 90        }
 91  
 92        // Copy any remaining entries of the second half
 93        while (i2 <= to)
 94        {
 95           b[j] = a[i2];
 96           i2++;
 97           j++;
 98        }
 99  
100        // Copy back from the temporary array
101        for (j = 0; j < n; j++)
102           a[from + j] = (E) b[j];
103     }
104  }