# Mergesort

• 05-09-2011, 05:59 PM
pauser
Mergesort
Hi!
I must sort a (cycle)DoubleLinkedList with MergeSort!
The code ist this:
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:
Code:

```1 2 3 4 5 6```
output:
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.