public class OptMergeSort {
    private static final int BREAKPOINT = 16;

    // sort: reorders the elements of <b>elts</b> so that they are in
    // increasing order.
    public static void sort(int[] elts) {
        int last;

        // First go through, doing insertion sort to sort the array in
        // pieces of BREAKPOINT elements.
        for(int first = 0; first < elts.length; first = last) {
            last = first + BREAKPOINT;
            if(last >= elts.length) last = elts.length;

            for(int i = first; i < last; i++) {
                int k = elts[i]; // store element i in k
                int j;
                for(j = i - 1; j >= first && elts[j] > k; j--) {
                    elts[j + 1] = elts[j]; // shift elts[j] up one slot
                }
                elts[j + 1] = k; // place k into vacated slot
            }
        }

        if(elts.length <= BREAKPOINT) return;

        // Allocate a second array, since Mergesort needs a second array
        // into which to merge.
        int[] src = elts;
        int[] dst = new int[elts.length];

        // Now we'll iteratively double the sizes of the chunks of 
        // src which are sorted. We begin with BREAKPOINT, since we've
        // already handled those chunks with insertion sort.
        for(int len = BREAKPOINT; len < elts.length; len *= 2) {
            for(int first = 0; first < elts.length; first = last) {
                int second = first + len;
                if(second >= elts.length) {
                    System.arraycopy(src, first, dst, first,
                        elts.length - first);
                    break;
                }
                last = second + len;
                if(last > elts.length) last = elts.length;
                merge(dst, src, first, second, last);
            }

            // dst has what we want. We swap src and dst so that, in the
            // next iteration, src has the sorted elements, and we
            // re-use dst (previously src) as the destination array.
            int[] tmp = src;
            src = dst;
            dst = tmp;
        }

        // If it happens that we've sorted into the wrong array, we copy
        // back into the original.
        if(src != elts) {
            System.arraycopy(src, 0, elts, 0, elts.length);
        }
    }

    // merge: merges arrays <b>a</b> and <b>b</b>, placing the result into the
    // array <b>dest</b>. This only works if both <b>a</b> and <b>b</b> are already in
    // increasing order.
    private static void merge(int[] dst, int[] src, int i, int j, int j_last) {
        int i_last = j;
        int k = i;

        if(i < i_last && j < j_last) {
            while(true) {
                if(src[i] < src[j]) {
                    dst[k++] = src[i++];
                    if(i >= i_last) break;
                } else {
                    dst[k++] = src[j++];
                    if(j >= j_last) break;
                }
            }
        }

        if(i < i_last) {
            System.arraycopy(src, i, dst, k, i_last - i);
        }
        if(j < j_last) {
            System.arraycopy(src, j, dst, k, j_last - j);
        }
    }
}