01: package org.swingml.treetablebrowser.ext;
02:
03: public abstract class MergeSort extends Object {
04: protected Object swapSpace[];
05: protected Object toSort[];
06:
07: public abstract int compareElementsAt(int beginLoc, int endLoc);
08:
09: protected void merge(int begin, int middle, int end) {
10: int firstHalf, secondHalf, count;
11: firstHalf = count = begin;
12: secondHalf = middle + 1;
13: while ((firstHalf <= middle) && (secondHalf <= end)) {
14: if (this .compareElementsAt(secondHalf, firstHalf) < 0)
15: swapSpace[count++] = toSort[secondHalf++];
16: else
17: swapSpace[count++] = toSort[firstHalf++];
18: }
19: if (firstHalf <= middle) {
20: while (firstHalf <= middle)
21: swapSpace[count++] = toSort[firstHalf++];
22: } else {
23: while (secondHalf <= end)
24: swapSpace[count++] = toSort[secondHalf++];
25: }
26: for (count = begin; count <= end; count++)
27: toSort[count] = swapSpace[count];
28: }
29:
30: protected void mergeSort(int begin, int end) {
31: if (begin != end) {
32: int mid;
33: mid = (begin + end) / 2;
34: this .mergeSort(begin, mid);
35: this .mergeSort(mid + 1, end);
36: this .merge(begin, mid, end);
37: }
38: }
39:
40: public void sort(Object array[]) {
41: if (array != null && array.length > 1) {
42: int maxLength;
43: maxLength = array.length;
44: swapSpace = new Object[maxLength];
45: toSort = array;
46: this .mergeSort(0, maxLength - 1);
47: swapSpace = null;
48: toSort = null;
49: }
50: }
51: }
|