public static <T> void swap(T[] a, int x, int y) {
    T t=a[x];
    a[x]=a[y];
    a[y]=t;
}

public static <T extends Comparable<? super T>> void mergeInOrder(T[] src, T[] dst, int p1, int p2, int p3, int p4) {
    if (src[p2].compareTo(src[p3])<=0) return; // already sorted!

    // cut away ends
    while (src[p1].compareTo(src[p3])<=0) p1++;
    while (src[p2].compareTo(src[p4])<=0) p4--;

    int i1=p1;
    int i3=p3;
    int di=p1;
    while(di<p4) {
        if (src[i1].compareTo(src[i3])<=0) {
            dst[di++]=src[i1++];
        } else {
            dst[di++]=src[i3++];
            if (i3>p4) {
                System.arraycopy(src,i1,dst,di,p2-i1+1);
                break;
            }
        }
    }

    System.arraycopy(dst, p1, src, p1, (p4-p1)+1);
}

public static <T extends Comparable<? super T>> void mergeSort(T[] src, T[] dst, int start, int end) {
    if (start+1>=end) {
        if (start>=end) return;
        if (src[start].compareTo(src[end])>0) {
            swap(src,start,end);
        }
        return;
    }

    int middle=(start+end)/2;
    mergeSort(src,dst,start, middle);
    mergeSort(src,dst,middle+1, end);
    mergeInOrder(src,dst,start,middle,middle+1,end);
}

private static ThreadLocal<Comparable<?>[]> mergeSortTemp=new ThreadLocal<Comparable<?>[]>();

@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] src) {
    int length=src.length;
    Comparable<?>[] temp=mergeSortTemp.get();
    if ((temp==null)||(temp.length<length)) {
        temp=new Comparable[length*3/2];
        mergeSortTemp.set(temp);
    }
    mergeSort(src,(T[])temp,0,length-1);
}