Merge Sort

    public int[] MergeSort(int[] a)    {
        int mid = a.length/2;
        if(mid<1)    return a;
        int[] left = new int[mid];
        int i=0;
        for(; i<left.length; i++)
            left[i]=a[i];
        left = MergeSort(left);
        int[] right = new int[(a.length%2==1)?(mid+1):mid];
        for(int j=0; j<right.length; j++)    {
            right[j]=a[i];
            i++;
        }
        right = MergeSort(right);
        return Merge(left, right);
    }
    private int[] Merge(int[] left, int[] right)    {
        int i, j, k;    i=j=k=0;
        int[] merged = new int[left.length+right.length];
        while(i<left.length && j<right.length)    {
            if(left[i]<=right[j])    {
                merged[k]=left[i];
                i++;
            }    else if(left[i]>right[j])    {
                merged[k]=right[j];
                j++;
            }
            k++;
        }
        while(i<left.length)    {
            merged[k]=left[i];
            i++; k++;
        }
        while(j<right.length)    {
            merged[k]=right[j];
            j++; k++;
        }
        return merged;
    }