<![CDATA[
CSE143 Program Example handout #15
Code for merge sort
-------------------
// post: list is in sorted (nondecreasing) order
public static void sort(Queue<String> list) {
if (list.size() > 1) {
Queue<String> half1 = new LinkedList<String>();
Queue<String> half2 = new LinkedList<String>();
int size1 = list.size() / 2;
int size2 = list.size() - size1;
for (int i = 0; i < size1; i++) {
half1.add(list.remove());
}
for (int i = 0; i < size2; i++) {
half2.add(list.remove());
}
sort(half1);
sort(half2);
mergeInto(list, half1, half2);
}
}
// pre : result is empty; list1 is sorted; list2 is sorted
// post: result contains the result of merging the sorted lists;
// list1 is empty; list2 is empty
private static void mergeInto(Queue<String> result,
Queue<String> list1,
Queue<String> list2) {
while (!list1.isEmpty() && !list2.isEmpty()) {
if (list1.peek().compareTo(list2.peek()) <= 0) {
result.add(list1.remove());
} else {
result.add(list2.remove());
}
}
while (!list1.isEmpty()) {
result.add(list1.remove());
}
while (!list2.isEmpty()) {
result.add(list2.remove());
}
}
Sample Execution on Linux Time-Sharing System (with n = 1 million)
------------------------------------------------------------------
linked list sort took 1.752 seconds
collections sort took 1.043 seconds
Ratio = 1.6797698945349953
lists match and sort is stable
]]>