<![CDATA[
// Stuart Reges handout #15
// 4/22/05
//
// This program has a method sort that can sort any Collection. It uses a
// mergesort algorithm with LinkedLists. Method main tests it by constructing
// two ArrayLists containing Strings. It compares the time used by this sort
// versus Collections.sort.
import java.util.*;
public class Sorter {
public static void main(String[] args) {
int n = 100000;
ArrayList list1 = new ArrayList();
ArrayList list2 = new ArrayList();
Random r = new Random();
for (int i = 0; i < n; i++) {
String text = "some text with #" + r.nextInt(2 * n);
list1.add(text);
list2.add(text);
}
long start = System.currentTimeMillis();
sort(list1);
double elapsed1 = (System.currentTimeMillis() - start)/1000.0;
System.out.println("linked list sort took " + elapsed1 + " seconds");
System.out.println();
start = System.currentTimeMillis();
Collections.sort(list2);
double elapsed2 = (System.currentTimeMillis() - start)/1000.0;
System.out.println("collections sort took " + elapsed2 + " seconds");
System.out.println();
System.out.println("Ratio = " + elapsed1 / elapsed2);
for (int i = 0; i < n; i++)
if (list1.get(i) != list2.get(i))
throw new RuntimeException("lists don't match");
}
// pre : all elements of the list implement Comparable and are mutually
// comparable
// post: list is in sorted order
public static void sort(Collection list) {
LinkedList data = new LinkedList(list);
sort(data);
list.clear();
list.addAll(data);
}
// pre : all elements of the list implement Comparable and are mutually
// comparable
// post: list is in sorted order
public static void sort(LinkedList list) {
if (list.size() > 1) {
LinkedList half1 = new LinkedList();
LinkedList half2 = new LinkedList();
int size1 = list.size() / 2;
int size2 = list.size() - size1;
for (int i = 0; i < size1; i++)
half1.addLast(list.removeFirst());
for (int i = 0; i < size2; i++)
half2.addLast(list.removeFirst());
sort(half1);
sort(half2);
mergeInto(list, half1, half2);
}
}
// pre : result is empty; all elements in list1 and list2 implement
// Comparable and are mutually comparable; list1 is sorted;
// list2 is sorted
// post: result contains the result of merging the sorted lists;
// list1 is empty; list2 is empty
public static void mergeInto(LinkedList result, LinkedList list1,
LinkedList list2) {
while (!list1.isEmpty() && !list2.isEmpty()) {
Comparable value1 = (Comparable)list1.getFirst();
Comparable value2 = (Comparable)list2.getFirst();
if (value1.compareTo(value2) <= 0)
result.addLast(list1.removeFirst());
else
result.addLast(list2.removeFirst());
}
while (!list1.isEmpty())
result.addLast(list1.removeFirst());
while (!list2.isEmpty())
result.addLast(list2.removeFirst());
}
}
]]>