<![CDATA[
CSE143 Program Example handout #17
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
public 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 5.122 seconds
collections sort took 2.15 seconds
Ratio = 2.382325581395349
lists match and sort is stable
More Efficient Version of sort That Returns Sorted List
-------------------------------------------------------
public static Queue<String> sort(Queue<String> list) {
if (list.size() > 1) {
Queue<String> half1 = new LinkedList<String>();
int size1 = list.size() / 2;
for (int i = 0; i < size1; i++)
half1.add(list.remove());
Queue<String> half2 = list;
list = new LinkedList<String>();
half1 = sort(half1);
half2 = sort(half2);
mergeInto(list, half1, half2);
}
return list;
}
]]>