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.