MergeSort performance

[davidmccabe]

i have recently been given an assignment involving the use of sorting algorithms (mergesort and quicksort). i have been given the code for mergesort and had to create the quicksort. this is what i have come up with.


public class QuickSortLists
{
static String spaces = "";
public static void main(String[] args)
{
UnorderedLinkedList l1 = new UnorderedLinkedList();

l1.addToFront(new Integer(67));
l1.addToFront(new Integer(12));
l1.addToFront(new Integer(81));
l1.addToFront(new Integer(29));
l1.addToFront(new Integer(56));
l1.addToFront(new Integer(11));
l1.addToFront(new Integer(8));
l1.addToFront(new Integer(49));

System.out.println("Sorting " + l1);

quickSort(l1);

System.out.println(" Sorted List " + l1);
}


public static void quickSort(UnorderedLinkedList L)

{ UnorderedLinkedList leftList, rightList;
leftList = new UnorderedLinkedList();
rightList = new UnorderedLinkedList();
Integer I1, I2;

Comparable pivot, element;
pivot = (Comparable) L.first();

System.out.println("PIVOT IS: " + pivot);

while (!L.isEmpty())
{
element = (Comparable) L.removeFirst();
if(element.compareTo(pivot) < 0)
leftList.addToFront(element);
else rightList.addToFront(element);

}

System.out.print("This breaks down into List1 " + leftList);
System.out.println(" and List2 " + rightList);

System.out.println("\nSorting " + leftList);
quickSort(leftList);

System.out.println("\nSorting " + rightList);
quickSort(rightList);

System.out.print("Merging " + leftList + " and " + rightList);

while((leftList.size() > 0) && (rightList.size() > 0))
{
I1 = (Integer) leftList.first();
I2 = (Integer) rightList.first();
if(I1.compareTo(I2) < 0)
{ L.addToRear(leftList.removeFirst());

}

else
{
L.addToRear(rightList.removeFirst());

}

}

while(leftList.size() > 0)

L.addToRear(leftList.removeFirst());


while (rightList.size() > 0)

L.addToRear(rightList.removeFirst());


System.out.println(" to give " + L);

}
}


however tihis code doesnt seem to come up with the correct results. it throws and exception when the leftList is empty, whihc isnt what i wanted. i have tried changing the conditions in the while loop but it doesnt make any difference.

Secondly i have been asked to confirm the theoretical predictions for the performance of the Mergesort technique, using the provided mergesort program. I have no idea what this means and would appreciated it tremendously if someone could help me.
I dont know if you can post attachments in this forum so i put the other classes needed in a zip file located atthis address.

thanks in advance

david

[cma]

Quick sort is not supposed to use temporaries to store its results, your quick sort looks more like merge-sort. Are you familiar with the algorithm?

First, partition the array/list by choosing any element as the pivot and moving all elements smaller then the pivot to the left half of the array/list and all elements greater then the pivot to the right half of the array/list.

Second, quick sort the elements that are smaller then the pivot.

Third, quick sort the elements that are larger then the pivot.

As for quick sort vs merge sort, as a rule-of-thumb, quick sort is generally faster since it doesn't need to allocate/deallocate temporary storage, however, with quick sort, if you don't choose good pivot's, then it can become as inefficient as selection/bubble sort.