Results 1 to 1 of 1
  1. #1
    cherrychives is offline Member
    Join Date
    Apr 2012
    Posts
    25
    Rep Power
    0

    Default Recursive merge sort really slow..

    My merge sort class receives a linked list and and sorts it recursively using.. merge sort.

    It works, but very, very slowly. The worst part is I know what (one of?) the problem(s) is, but I can't figure out how to fix it.

    So here it is:

    Java Code:
    private static intList mergeSort(intList list){
    	intList tempList1 = new intList(list.size / 2); //create 2 temporary linked lists to..
    	intList tempList2 = new intList(list.size / 2); //..hold half of the values each
    	intList mergedList = new intList(list.size);
    	while(list.first != null){ //loop while list still has values to be added to tempList1 or tempList2
    		tempList1.insertFirst(list.first.value); //add first value in list to tempList1
    		list.deleteFirst(); //delete first value in list
    		if(list.first != null){
    			tempList2.insertFirst(list.first.value); //add first value in list to tempList2 if not null
    			list.deleteFirst(); //delete first value in list
    		}
    	}
    	if(tempList1.first.nextNode != null){
    		tempList1 = mergeSort(tempList1); //use mergeSort again if tempList1 contains more than one node
    	}
    	if(tempList2.first.nextNode != null){
    		tempList2 = mergeSort(tempList2); //use mergeSort again if tempList2 contains more than one node
    	}
    	while(tempList1.first != null || tempList2.first != null){
    		if(tempList2.first == null || tempList1.first != null && tempList1.first.value < tempList2.first.value){
    			mergedList.insertLast(tempList1.first.value);	//
    			tempList1.deleteFirst();						// compare  first value in tempList1..
    		}													// ..with first value in tempList2..
    		else{												// ..and add the lowest of the two values..
    			mergedList.insertLast(tempList2.first.value);	// ..to the end of mergedList
    			tempList2.deleteFirst();						//
    		}
    	}
    	return mergedList;
    }
    I believe the problem is my InsertLast method, which LOOPS to the end of the list every time a new value is added to mergeSort, which adds a lot of time when working with a longer list:

    Java Code:
    public void insertLast(int x){
    	if(first == null){
    		insertFirst(x);
    		return;
    	}
    	intNode newNode = new intNode(x);
    	intNode current = first;
    	while(current.nextNode != null){
    		current = current.nextNode;
    	}
    	current.next = x;
    	current.nextNode = newNode;
    }
    I'm hoping someone with knowledge on linked lists and/or merge sort can help me find a better solution here.

    Thanks in advance.
    Last edited by cherrychives; 05-14-2012 at 05:09 PM.

Similar Threads

  1. Merge sort
    By Aivy in forum New To Java
    Replies: 3
    Last Post: 12-14-2011, 12:29 PM
  2. merge sort with recursive method (need help badlly!!)
    By zetalore in forum Advanced Java
    Replies: 0
    Last Post: 01-08-2011, 08:10 PM
  3. Using Merge Sort to sort an ArrayList of Strings
    By coldfire in forum New To Java
    Replies: 3
    Last Post: 03-13-2009, 02:03 AM
  4. Merge Sort in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 08:43 PM
  5. Merge Sort Help
    By Hollywood in forum New To Java
    Replies: 5
    Last Post: 01-30-2008, 04:26 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •