Mergesort

import java.util.Arrays;

public class MergeSort {


    static final int[] sort(int[] input)
    {
        if(input.length > 1)
        {
            /*Mitte ausrechnen*/
            int middle = (int)(input.length/2);

            /*Splitten*/
            int[] left = new int[middle];
            /*In das neue Array kopieren*/
            for(int i = 0; i < left.length; i++)
            {
                left[i] = input[i];
            }
            /*Splitten*/
            int[] right = new int[input.length - middle];
            /*In das neue Array kopieren*/
            for(int i = middle; i < input.length; i++)
            {
                right[i - middle] = input[i];
            }
            /*Die linke und rechte Hälfte sortieren (Das ist der Rekursiv-Schritt)*/
            left = sort(left);
            right = sort(right);
            /*Wenn beide sortiert sind, sie mergen und damit auch sortieren*/
            return merge(left,right);
        }
        else
        {
            /*Wenn wir eine length von 1 haben brauchen wir nicht sortieren, und können einfach returnen.
             * Hier ist der abbruch der rekursion*/
            return input;
        }
    }

    static final int[] merge(int[] left, int[] right)
    {
        int[] ret = new int[left.length + right.length];
        int i = 0;
        int j = 0;
        int index = 0;/*Das gleiche wie i + j*/
        while(i < left.length && j < right.length)
        {
            if(left[i] < right[j])
            {
                ret[index] = left[i];
                i++;
            }
            else
            {
                ret[index] = right[j];
                j++;
            }
            index++;
        }

        while( i < left.length)
        {
            ret[index] = left[i];
            i++;
            index++;
        }
        while( j < right.length)
        {
            ret[i + j] = right[j];
            j++;
            index++;
        }

        return ret;
    }

}