/* * %W% %E% * * Copyright 1997, 1998 Sun Microsystems, Inc. All Rights Reserved. * * Redistribution and use in source and binary forms, with or * without modification, are permitted provided that the following * conditions are met: * * - Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * - Redistribution in binary form must reproduce the above * copyright notice, this list of conditions and the following * disclaimer in the documentation and/or other materials * provided with the distribution. * * Neither the name of Sun Microsystems, Inc. or the names of * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * * This software is provided "AS IS," without a warranty of any * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY * EXCLUDED. SUN AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY * DAMAGES OR LIABILITIES SUFFERED BY LICENSEE AS A RESULT OF OR * RELATING TO USE, MODIFICATION OR DISTRIBUTION OF THIS SOFTWARE OR * ITS DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE * FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, * SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER * CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF * THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS * BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. * * You acknowledge that this software is not designed, licensed or * intended for use in the design, construction, operation or * maintenance of any nuclear facility. */ /** * An implementation of MergeSort, needs to be subclassed to provide a * comparator. * * @version %I% %G% * * @author Scott Violet */ public abstract class MergeSort extends Object { protected Object toSort[]; protected Object swapSpace[]; public void sort(Object array[]) { if(array != null && array.length > 1) { int maxLength; maxLength = array.length; swapSpace = new Object[maxLength]; toSort = array; this.mergeSort(0, maxLength - 1); swapSpace = null; toSort = null; } } public abstract int compareElementsAt(int beginLoc, int endLoc); protected void mergeSort(int begin, int end) { if(begin != end) { int mid; mid = (begin + end) / 2; this.mergeSort(begin, mid); this.mergeSort(mid + 1, end); this.merge(begin, mid, end); } } protected void merge(int begin, int middle, int end) { int firstHalf, secondHalf, count; firstHalf = count = begin; secondHalf = middle + 1; while((firstHalf <= middle) && (secondHalf <= end)) { if(this.compareElementsAt(secondHalf, firstHalf) < 0) swapSpace[count++] = toSort[secondHalf++]; else swapSpace[count++] = toSort[firstHalf++]; } if(firstHalf <= middle) { while(firstHalf <= middle) swapSpace[count++] = toSort[firstHalf++]; } else { while(secondHalf <= end) swapSpace[count++] = toSort[secondHalf++]; } for(count = begin;count <= end;count++) toSort[count] = swapSpace[count]; } }