package Sortieralgorithmen;

public class MergeSort {
    
    // WS 14/15 Lückentext:
    public static void sort(int[] numbers, int left, int right) {
        final int rightmost = right;
        final int leftmost = left;
        if (left >= right) return;

        // sort 
        int middle = left + (right-left)/2;
        sort(numbers, left, middle);
        sort(numbers, middle + 1, right);

        // merge 
        int[] sorted = new int[right - left + 1];
        right = middle + 1;
        for (int i = 0; i < sorted.length; i++) {
            if (left > middle || (right <= rightmost && 
                                  numbers[left] > numbers[right])) {
                sorted[i] = numbers[right];
                right++;
            } else {
                sorted[i] = numbers[left];
                left++;
            }
        }

        // store
        for (int i = 0; i < sorted.length; i++) {
            numbers[leftmost + i] = sorted[i];
        }
    }
}

/**
 * Mergesort Implementierung nach Vorlesung WS 16/17
 */
class List {

    public int info;
    public List next;

    public List(int info, List next) {
        this.info = info;
        this.next = next;
    }

    public List(int info) {
        this(info, null);
    }

    public void insert(int e) {
        next = new List(e, next);
    }

    public void delete() {
        if (next != null) {
            next = next.next;
        }
    }

    public String toString() {
        String result = "[" + info;
        for (List t = next; t != null; t = t.next) {
            result = result + ", " + t.info;
        }
        return result + "]";
    }

    public static boolean isEmpty(List l) {
        return l == null;
    }

    public static List arrayToList(int[] a) {
        List result = null;
        for (int i = a.length - 1; i >= 0; --i) {
            result = new List(a[i], result);
        }
        return result;
    }

    public int[] listToArray() {
        List t = this;
        int n = length();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = t.info;
            t = t.next;
        }
        return a;
    }

    private int length() {
        int result = 1;
        for (List t = next; t != null; t = t.next) {
            result++;
        }
        return result;
    }

    /**
     * Mergesort
     */
    public static List merge(List a, List b) {
        if (b == null) {
            return a;
        }
        if (a == null) {
            return b;
        }
        if (b.info > a.info) {
            a.next = merge(a.next, b);
            return a;
        } else {
            b.next = merge(a, b.next);
            return b;
        }
    }

    public static List sort(List a) {
        if (a == null || a.next == null) // max. ein Element
        {
            return a;
        }
        List b = a.half();  // halbieren
        a = sort(a);
        b = sort(b);
        return merge(a, b);
    }

    public List half() {
        int n = length();
        List t = this;
        for (int i = 0; i < n / 2 - 1; i++) {
            t = t.next;
        }
        List result = t.next;
        t.next = null;
        return result;
    }
}