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

[Belisarius]

On the theoretical performance, I'd count the number of times through the merge you had to go before you achieved the desired end result. Let me look at the code for a bit to see if I can spot what's going wrong.

[Belisarius]

pivot = (Comparable) L.first();

Ever wonder what would happen if L was empty? Bet this is what's causing your exception.

[davidmccabe]

would i have to use a count variable somewhere to count how many times mergesort is used?

when i try to change anythiong about the comparable pivot, i get errors saying it hasnt been declared properly.

please help

[Belisarius]

would i have to use a count variable somewhere to count how many times mergesort is used?

Yes, you would.

when i try to change anythiong about the comparable pivot, i get errors saying it hasnt been declared properly.

Have you considered checking to see if L actually contains anything? If it doesn't, why bother with pivot at all?