001    package util;
002    
003    /**
004     * An implementation of MergeSort, needs to be subclassed to compare the terms.
005     *
006     * @author Scott Violet
007     */
008    public abstract class MergeSort extends Object {
009        protected Object           toSort[];
010        protected Object           swapSpace[];
011    
012        public void sort(Object array[]) {
013            if(array != null && array.length > 1)
014            {
015                int             maxLength;
016    
017                maxLength = array.length;
018                swapSpace = new Object[maxLength];
019                toSort = array;
020                this.mergeSort(0, maxLength - 1);
021                swapSpace = null;
022                toSort = null;
023            }
024        }
025    
026        public abstract int compareElementsAt(int beginLoc, int endLoc);
027    
028        protected void mergeSort(int begin, int end) {
029            if(begin != end)
030            {
031                int           mid;
032    
033                mid = (begin + end) / 2;
034                this.mergeSort(begin, mid);
035                this.mergeSort(mid + 1, end);
036                this.merge(begin, mid, end);
037            }
038        }
039    
040        protected void merge(int begin, int middle, int end) {
041            int           firstHalf, secondHalf, count;
042    
043            firstHalf = count = begin;
044            secondHalf = middle + 1;
045            while((firstHalf <= middle) && (secondHalf <= end))
046            {
047                if(this.compareElementsAt(secondHalf, firstHalf) < 0)
048                    swapSpace[count++] = toSort[secondHalf++];
049                else
050                    swapSpace[count++] = toSort[firstHalf++];
051            }
052            if(firstHalf <= middle)
053            {
054                while(firstHalf <= middle)
055                    swapSpace[count++] = toSort[firstHalf++];
056            }
057            else
058            {
059                while(secondHalf <= end)
060                    swapSpace[count++] = toSort[secondHalf++];
061            }
062            for(count = begin;count <= end;count++)
063                toSort[count] = swapSpace[count];
064        }
065    }