01: package net.sf.memoranda.ui.treetable;
02:
03: /*
04: * MergeSort.java
05: *
06: * Copyright (c) 1998 Sun Microsystems, Inc. All Rights Reserved.
07: *
08: * This software is the confidential and proprietary information of Sun
09: * Microsystems, Inc. ("Confidential Information"). You shall not
10: * disclose such Confidential Information and shall use it only in
11: * accordance with the terms of the license agreement you entered into
12: * with Sun.
13: *
14: * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
15: * SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
16: * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
17: * PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES
18: * SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
19: * THIS SOFTWARE OR ITS DERIVATIVES.
20: *
21: */
22:
23: /**
24: * An implementation of MergeSort, needs to be subclassed to
25: * compare the terms.
26: *
27: * @author Scott Violet
28: */
29: public abstract class MergeSort extends Object {
30: protected Object toSort[];
31: protected Object swapSpace[];
32:
33: public void sort(Object array[]) {
34: if (array != null && array.length > 1) {
35: int maxLength;
36:
37: maxLength = array.length;
38: swapSpace = new Object[maxLength];
39: toSort = array;
40: this .mergeSort(0, maxLength - 1);
41: swapSpace = null;
42: toSort = null;
43: }
44: }
45:
46: public abstract int compareElementsAt(int beginLoc, int endLoc);
47:
48: protected void mergeSort(int begin, int end) {
49: if (begin != end) {
50: int mid;
51:
52: mid = (begin + end) / 2;
53: this .mergeSort(begin, mid);
54: this .mergeSort(mid + 1, end);
55: this .merge(begin, mid, end);
56: }
57: }
58:
59: protected void merge(int begin, int middle, int end) {
60: int firstHalf, secondHalf, count;
61:
62: firstHalf = count = begin;
63: secondHalf = middle + 1;
64: while ((firstHalf <= middle) && (secondHalf <= end)) {
65: if (this .compareElementsAt(secondHalf, firstHalf) < 0)
66: swapSpace[count++] = toSort[secondHalf++];
67: else
68: swapSpace[count++] = toSort[firstHalf++];
69: }
70: if (firstHalf <= middle) {
71: while (firstHalf <= middle)
72: swapSpace[count++] = toSort[firstHalf++];
73: } else {
74: while (secondHalf <= end)
75: swapSpace[count++] = toSort[secondHalf++];
76: }
77: for (count = begin; count <= end; count++)
78: toSort[count] = swapSpace[count];
79: }
80: }
|