Mergesort

**pauser** · 05-09-2011, 05:59 PM

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:

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!