Untitled

package ads1ss11.pa1;


/**
 * Sorter Klasse in der die Methode {@link #mergesort(DoublyLinkedList, int)}
 * implementiert werden soll.
 *
 * <p>
 * In dieser Klasse m&uuml;ssen Sie Ihren Code einf&uuml;gen und die Method
 * {@link #mergesort(DoublyLinkedList, int)} implementieren.
 * </p>
 *
 * <p>
 * Sie k&ouml;nnen beliebige neue Variablen und Methoden in dieser Klasse
 * hinzuf&uuml;gen.
 * </p>
 */

public class Sorter {

        /**
         * MergeSort Implementierung
         *
         * @param in Unsortierte Eingabefolge
         * @param numOfElements Gr&ouml;&szlig;e der Eingabefolge
         * @return Sortiterte Eingabefolge
         */
        public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) {
                ListElement end = split(in.first, numOfElements);
                in.first = end.next;
                return in;
        }

        private ListElement split(ListElement start,int length){
                if(length==1)return start;
                int half = length/2;
                ListElement a = split(start,half);
                ListElement b = split(a.next,length-half);

                return merge(a,b,half,length);
        }


        private ListElement merge(ListElement mid, ListElement end, int half, int length){
                ListElement LElement=mid,RElement=end;
                int l = half, r=length;
                while(l>0 && r > half){
                        if(LElement.getKey()<=RElement.getKey()){
                                RElement = RElement.prev;
                                r--;
                        }else{
                                ListElement LLinkerNachbar = LElement.prev;
                                ListElement RrechterNachbar = RElement.next;

                                LLinkerNachbar.next = LElement.next;
                                LElement.next.prev = LLinkerNachbar;

                                RElement.next = LElement;
                                LElement.prev = RElement;

                                RrechterNachbar.prev = LElement;
                                LElement.next = RrechterNachbar;

                                if(RElement==end){
                                        end = LElement;
                                }

                                LElement = LElement.prev;
                                l--;
                        }
                }
                return end;
        }
}