Results 1 to 2 of 2

Thread: Mergesort

  1. #1
    pauser is offline Member
    Join Date
    Apr 2010
    Posts
    7
    Rep Power
    0

    Default Mergesort

    Hi!
    I must sort a (cycle)DoubleLinkedList with MergeSort!
    The code ist this:
    PHP Code:
    public class Sorter {
    	public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) {
    		in.first = split(in.first, 1,numOfElements);
    		return in;
    	}
    	
    	private ListElement split(ListElement first, int l, int r){
            if(l<r){ 
                int m = (l+r)/2;
                ListElement left = first;
                ListElement right = first;
                for(int i=1;i<=m;i++){
                right = right.next;
                }
                ListElement r_left = split(left,l,m);
                ListElement r_right = split(right,m+1,r);
                return merge(r_left,r_right);
            }
            return first;
    	}
    
    	private ListElement merge(ListElement left, ListElement right){
    		System.out.println("left="+left+" right="+right);
    		return right;
    	}
    
    }
    input:
    Java Code:
    1
    2
    3
    4
    5
    6
    output:
    Java Code:
    left=1 right=2
    left=2 right=3
    left=4 right=2
    left=2 right=3
    left=3 right=3
    I tried to split the elements with a split method but after running, the programm gives me this result !
    My question is : is that right what i did, because its giving me more than expected(this idea should work in theory)
    - and how do I merge the elements. At the moment I can only merge 2 elements for each call, how do I merge them all.I dont need the whole method , just the idea how it hapens with mergesort in (cycle)DoubleLinkedList.


    Explanation:
    Class ListElement has a pointer ListElement next and a pointer ListElement prev.
    and
    DoublyLinkedList ist just the head of the list. It has just ListElement first.

    Please help me!
    Last edited by pauser; 05-09-2011 at 06:31 PM.

  2. #2
    pauser is offline Member
    Join Date
    Apr 2010
    Posts
    7
    Rep Power
    0

Similar Threads

  1. mergesort recursion
    By Yakg in forum New To Java
    Replies: 13
    Last Post: 02-20-2011, 06:58 PM
  2. help with mergesort
    By desconocido in forum New To Java
    Replies: 5
    Last Post: 09-15-2010, 03:56 AM
  3. mergeSort
    By Blue_beaver in forum New To Java
    Replies: 2
    Last Post: 10-11-2009, 10:55 PM

Posting Permissions

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