    001: import java.util.*;
    002:
    003: /**
    004:    This class carries out the merge sort algorithm.
    005: */
    006: public class MergeSorter
    007: {
    008:    /**
    009:       Sorts an array, using the merge sort algorithm.
    010:       @param a the array to sort
    011:       @param comp the comparator to compare array elements
    012:    */
    013:    public static void sort(Object[] a, Comparator comp)
    014:    {
    015:       mergeSort(a, 0, a.length - 1, comp);
    016:    }
    017:
    018:    /**
    019:       Sorts a range of an array, using the merge sort
    020:       algorithm.
    021:       @param a the array to sort
    022:       @param from the first index of the range to sort
    023:       @param to the last index of the range to sort
    024:       @param comp the comparator to compare array elements
    025:    */
    026:    private static void mergeSort(Object[] a, int from, int to,
    027:       Comparator comp)
    028:    {
    029:       if (from == to) return;
    030:       int mid = (from + to) / 2;
    031:        // sort the first and the second half
    032:       mergeSort(a, from, mid, comp);
    033:       mergeSort(a, mid + 1, to, comp);
    034:       merge(a, from, mid, to, comp);
    035:    }
    036:
    037:    /**
    038:       Merges two adjacent subranges of an array
    039:       @param a the array with entries to be merged
    040:       @param from the index of the first element of the
    041:          first range
    042:       @param mid the index of the last element of the
    043:          first range
    044:       @param to the index of the last element of the
    045:          second range
    046:       @param comp the comparator to compare array elements
    047:    */
    048:    private static void merge(Object[] a,
    049:       int from, int mid, int to, Comparator comp)
    050:    {
    051:       int n = to - from + 1;
    052:          // size of the range to be merged
    053:
    054:       // merge both halves into a temporary array b
    055:       Object[] b = new Object[n];
    056:
    057:       int i1 = from;
    058:          // next element to consider in the first range
    059:       int i2 = mid + 1;
    060:          // next element to consider in the second range
    061:       int j = 0;
    062:          // next open position in b
    063:
    064:       // as long as neither i1 nor i2 past the end, move
    065:       // the smaller element into b
    066:       while (i1 <= mid && i2 <= to)
    067:       {
    068:          if (comp.compare(a[i1], a[i2]) < 0)
    069:          {
    070:             b[j] = a[i1];
    071:             i1++;
    072:          }
    073:          else
    074:          {
    075:             b[j] = a[i2];
    076:             i2++;
    077:          }
    078:          j++;
    079:       }
    080:
    081:       // note that only one of the two while loops
    082:       // below is executed
    083:
    084:       // copy any remaining entries of the first half
    085:       while (i1 <= mid)
    086:       {
    087:          b[j] = a[i1];
    088:          i1++;
    089:          j++;
    090:       }
    091:
    092:       // copy any remaining entries of the second half
    093:       while (i2 <= to)
    094:       {
    095:          b[j] = a[i2];
    096:          i2++;
    097:          j++;
    098:       }
    099:
    100:       // copy back from the temporary array
    101:       for (j = 0; j < n; j++)
    102:          a[from + j] = b[j];
    103:    }
    104: }