001 /*
002 * LAPIS lightweight structured text processing system
003 *
004 * Copyright (C) 1998-2002 Carnegie Mellon University,
005 * Copyright (C) 2003 Massachusetts Institute of Technology.
006 * All rights reserved.
007 *
008 * This library is free software; you can redistribute it
009 * and/or modify it under the terms of the GNU General
010 * Public License as published by the Free Software
011 * Foundation, version 2.
012 *
013 * LAPIS homepage: http://graphics.lcs.mit.edu/lapis/
014 */
015
016 package lapisx.sort;
017
018 import java.util.Vector;
019
020 public abstract class MergeSort {
021
022 public static void sort (Sortable a) {
023 Vector buffer = new Vector ();
024 buffer.setSize (a.size ());
025 sort (a, 0, a.size()-1, buffer);
026 }
027
028 public static void sort (Sortable a, int p, int r, Vector buffer) {
029 if (p < r) {
030 int q = (p + r)/2;
031 sort (a, p, q, buffer);
032 sort (a, q+1, r, buffer);
033 merge (a, p, q, r, buffer);
034 }
035 }
036
037 private static void merge (Sortable a, int p, int q, int r, Vector buffer) {
038 int k = 0;
039 int i = p;
040 int j = q + 1;
041 Object objI = a.get (i);
042 Object objJ = a.get (j);
043 while (true) {
044 if (a.compare (objI, objJ) <= 0) {
045 buffer.setElementAt (objI, k);
046 ++k;
047 ++i;
048 if (i > q)
049 break;
050 objI = a.get (i);
051 } else {
052 buffer.setElementAt (objJ, k);
053 ++k;
054 ++j;
055 if (j > r)
056 break;
057 objJ = a.get (j);
058 }
059 }
060
061 while (i <= q) {
062 buffer.setElementAt (a.get (i), k);
063 ++k;
064 ++i;
065 }
066
067 while (j <= r) {
068 buffer.setElementAt (a.get (j), k);
069 ++k;
070 ++j;
071 }
072
073 for (i = 0; i < k; ++i)
074 a.set (p + i, buffer.elementAt (i));
075 }
076
077
078 public static SortableList sort (SortableList l) {
079 return sort (l, count (l));
080 }
081
082 public static SortableList sort (SortableList l, int n) {
083 if (n < 2)
084 return l;
085
086 int half = n/2;
087 SortableList l1 = l;
088 SortableList l1End = traverse (l, half-1);
089 SortableList l2 = l1End.next ();
090 l1End.setNext (null);
091
092 // l1 is now a list of half elements,
093 // l2 is now a list of n-half elements.
094 // Sort l1 and l2 separately and merge them.
095 l1 = sort (l1, half);
096 l2 = sort (l2, n-half);
097
098 return merge (l1, l2);
099 }
100
101 private static SortableList merge (SortableList l1, SortableList l2) {
102 SortableList header = new DummySortableList ();
103 SortableList l = header;
104
105 while (l1 != null && l2 != null) {
106 if(l1.compareTo (l2) <= 0) {
107 l.setNext (l1);
108 l = l1;
109 l1 = l1.next ();
110 }
111 else {
112 l.setNext (l2);
113 l = l2;
114 l2 = l2.next ();
115 }
116 }
117
118 if (l1 != null)
119 l.setNext (l1);
120 else if (l2 != null)
121 l.setNext (l2);
122 else
123 l.setNext (null);
124
125 return header.next ();
126 }
127
128 static class DummySortableList implements SortableList {
129 SortableList nextPtr;
130 public Object get () { return null; }
131 public SortableList next () { return nextPtr; }
132 public void setNext (SortableList l) { nextPtr = l; }
133 public int compareTo (SortableList l) { return 0; }
134 }
135
136 private static SortableList traverse (SortableList l, int n) {
137 while (n > 0) {
138 l = l.next ();
139 --n;
140 }
141 return l;
142 }
143
144 private static int count (SortableList l) {
145 int n = 0;
146 for (SortableList p = l; p != null; p = p.next ())
147 ++n;
148 return n;
149 }
150
151 public static void test (String[] args) {
152 StringSortableList list = StringSortableList.make (args);
153 list = (StringSortableList)MergeSort.sort (list);
154 System.out.print ("list sort: ");
155 if (list != null)
156 list.dump ();
157 System.out.println ();
158
159 Vector v = new Vector ();
160 for (int i = 0; i < args.length; ++i)
161 v.addElement (args[i]);
162 MergeSort.sort (new SortableVector (v));
163 System.out.print ("array sort: ");
164 for (int i = 0; i < v.size (); ++i)
165 System.out.print (v.elementAt (i) + " ");
166 System.out.println ();
167
168
169 }
170
171 public static void main (String[] args) {
172 if (args.length > 0)
173 test (args);
174 else {
175 test (new String[] {"b", "d", "a", "c"});
176 test (new String[] {"a", "b", "c", "d"});
177 test (new String[] {"d", "c", "b", "a"});
178
179 test (new String[] {"a", "b", "c"});
180 test (new String[] {"c", "b", "a"});
181
182 test (new String[] {"a", "b"});
183 test (new String[] {"b", "a"});
184
185 test (new String[] {"a"});
186
187 test (new String[] {});
188
189 String[] random = new String[100];
190 for (int i = 0; i < random.length; ++i)
191 random[i] = String.valueOf ((char)('a' + 26 * Math.random ()));
192 test (random);
193 }
194 }
195 }