MergeSort performance

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.

Code:

---

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

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.