3-way merge sort in Java

All those numerous merge sorts split the range in two halves. This is a modification that splits each range into 3 subranges. My demo suggests that 3-way merge sort is pretty efficient on large arrays.

So, what do you think?

Arrays.java:

package net.coderodde.util;

/**
 * @author Rodion Efremov
 * @version 2014.12.17
 */
public class Arrays {

    private static final int INSERTION_SORT_THRESHOLD = 8;

    /**
     * Sorts the entire input array. 
     */
    public static final <E extends Comparable<? super E>>
        void sort(final E[] array) {
        sort(array, 0, array.length);       
    }

    /**
     * Sorts a specific range in the input array.
     */
    public static final <E extends Comparable<? super E>> 
        void sort(final E[] array, final int fromIndex, final int toIndex) {
        final int RANGE_LENGTH = toIndex - fromIndex;

        if (RANGE_LENGTH < 2) {
            // Trivially sorted or indices are ass-backwards.
            return;
        }

        final E[] buffer = array.clone();
        sortImpl(buffer, array, fromIndex, toIndex);
    }

    private static <E extends Comparable<? super E>>
            void sortImpl(final E[] source,
                          final E[] target,
                          final int fromIndex,
                          final int toIndex) {
        final int RANGE_LENGTH = toIndex - fromIndex;

        if (RANGE_LENGTH < INSERTION_SORT_THRESHOLD) {
            // We need slightly larger range length than two elements in order
            // to avoid infinite recursion and, thus, stack overflow.
            for (int i = fromIndex + 1; i < toIndex; ++i) {
                int j = i - 1;

                while (j >= fromIndex && target[j].compareTo(target[j + 1]) > 0) {
                    final E tmp = target[j];
                    target[j] = target[j + 1];
                    target[j + 1] = tmp;
                    --j;
                }
            }

            return;
        }

        final int MID1 = fromIndex + RANGE_LENGTH / 3;
        final int MID2 = MID1 + RANGE_LENGTH / 3;

        sortImpl(target, source, fromIndex, MID1);
        sortImpl(target, source, MID1, MID2);
        sortImpl(target, source, MID2, toIndex);

        merge(source, target, fromIndex, MID1, MID2, toIndex);
    }

    private static <E extends Comparable<? super E>>
            void merge(final E[] source,
                       final E[] target,
                       final int p1,
                       final int p2,
                       final int p3,
                       final int p4) {
        int i = p1;
        int idx1 = p1;           
        int idx2 = p2;           
        int idx3 = p3;

        while (idx1 < p2 && idx2 < p3 && idx3 < p4) {
            if (source[idx3].compareTo(source[idx1]) < 0) {
                if (source[idx3].compareTo(source[idx2]) < 0) {
                    target[i++] = source[idx3++];
                } else {
                    target[i++] = source[idx2++];
                }
            } else if (source[idx1].compareTo(source[idx2]) <= 0) {
                target[i++] = source[idx1++];
            } else {
                target[i++] = source[idx2++];
            }
        }

        while (idx1 < p2 && idx2 < p3) {
            target[i++] = source[idx1].compareTo(source[idx2]) <= 0 ?
                          source[idx1++] :
                          source[idx2++];
        }

        while (idx2 < p3 && idx3 < p4) {
            target[i++] = source[idx2].compareTo(source[idx3]) <= 0 ?
                          source[idx2++] :
                          source[idx3++];
        }

        while (idx1 < p2 && idx3 < p4) {
            target[i++] = source[idx1].compareTo(source[idx3]) <= 0 ?
                          source[idx1++] :
                          source[idx3++];
        }

        while (idx1 < p2) { target[i++] = source[idx1++]; }
        while (idx2 < p3) { target[i++] = source[idx2++]; }
        while (idx3 < p4) { target[i++] = source[idx3++]; }
    }

    /**
     * Checks whether all given arrays are of the same length and has identical
     * references at every corresponding array components.
     */
    public static final <E> boolean arraysEqual(final E[]... arrays) {
        if (arrays.length < 2) {
            return true;
        }

        for (int i = 0; i < arrays.length - 1; ++i) {
            if (arrays[i].length != arrays[i + 1].length) {
                return false;
            }
        }

        for (int idx = 0; idx < arrays[0].length; ++idx) {
            for (int i = 0; i < arrays.length - 1; ++i) {
                if (arrays[i][idx] != arrays[i + 1][idx]) {
                    return false;
                }
            }
        }

        return true;
    }
}

Demo.java:

package net.coderodde.util;

import java.util.Random;

public class Demo {

    private static final int N = 10000000;

    public static void main(final String... args) {   
        final long seed = System.currentTimeMillis();
        System.out.println("Seed: " + seed);

        final Random rnd = new Random(seed);
        Integer[] array1 = getRandomIntegerArray(N, -30, 30, rnd);
        Integer[] array2 = array1.clone();

        System.out.print("My 3-way merge sort:     ");
        long ta1 = System.currentTimeMillis();
        net.coderodde.util.Arrays.sort(array1);
        long tb1 = System.currentTimeMillis();

        System.out.println((tb1 - ta1) + " ms.");

        System.out.print("java.util.Arrays.sort(): ");
        long ta2 = System.currentTimeMillis();
        java.util.Arrays.sort(array2);
        long tb2 = System.currentTimeMillis();

        System.out.println((tb2 - ta2) + " ms.");

        System.out.println("Sorted arrays equal: " + 
                Arrays.arraysEqual(array1, array2));
    }

    private static Integer[] getRandomIntegerArray(final int size, 
                                                   final int min,
                                                   final int max,
                                                   final Random rnd) {
        final Integer[] array = new Integer[size];

        for (int i = 0; i < size; ++i) {
            array[i] = rnd.nextInt(max - min + 1) + min;
        }

        return array;
    }
}