Merge Sort

public class MergeSort {

    public static int[] sort(int[] arr)
    {
        if (arr.length == 1)
            return arr;

        int middle = arr.length / 2;
        int[] left = new int[middle];
        int[] right = new int[arr.length - middle];
        
        for (int i =0;i<middle;i++)
            left[i]=arr[i];

        for (int i = 0; i < right.length;i++)
            right[i]=arr[i+middle];

        left = sort(left);
        right = sort(right);

        if (left[left.length-1] > right[0])
            return merge(left,right);
        else
            return append(left,right);
    }

    public static int[] merge(int[] left, int[] right)
    {
        int[] result = new int[left.length + right.length];
        int lPtr=0;
        int rPtr=0;
        int resultPtr=0;

        while (lPtr < left.length && rPtr < right.length)
        {
            if (left[lPtr] < right[rPtr]){
                result[resultPtr]=left[lPtr];
                lPtr++;
                resultPtr++;
            } else {
                result[resultPtr]=right[rPtr];
                rPtr++;
                resultPtr++;
            }
        }

        if (lPtr == left.length)
        {
            while (rPtr != right.length)
                result[resultPtr++]=right[rPtr++];
        } else {
            while (lPtr != left.length)
                result[resultPtr++]=left[lPtr++];
        }

        return result;
    }

    public static int[] append(int[] left,int[] right)
    {
        int[] result = new int[left.length + right.length];
        for (int i = 0;i<left.length;i++)
            result[i]=left[i];

        for (int i = 0;i<right.length;i++)
            result[i+left.length]=right[i];

        return result;
    }
}