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