Method mergeSort

vm/JavaAPI/src/java/util/Arrays.java:2639–2704

Performs a sort on the section of the array between the given indices using a mergesort with exponential search algorithm (in which the merge is performed by exponential search). n log(n) performance is guaranteed and in the average case it will be faster then any mergesort in which the merge is per

(Object[] in, Object[] out, int start,
            int end)

     *            the end index + 1
     */
    @SuppressWarnings("unchecked")
    private static void mergeSort(Object[] in, Object[] out, int start,
            int end) {
        int len = end - start;
        
        Object o = in[start];
        // use insertion sort for small arrays
        if (len <= SIMPLE_LENGTH) {
            for (int i = start + 1; i < end; i++) {
                java.lang.Comparable<Object> current = 
                            (java.lang.Comparable<Object>) out[i];
                Object prev = out[i - 1];
                if (current.compareTo(prev) < 0) {
                    int j = i;
                    do {
                        out[j--] = prev;
                    } while (j > start
                            && current.compareTo(prev = out[j - 1]) < 0);
                    out[j] = current;
                }
            }
            return;
        }
        int med = (end + start) >>> 1;
        mergeSort(out, in, start, med);
        mergeSort(out, in, med, end);

        // merging

        // if arrays are already sorted - no merge
        if (((java.lang.Comparable<Object>) in[med - 1]).compareTo(in[med]) <= 0) {
            System.arraycopy(in, start, out, start, len);
            return;
        }
        int r = med, i = start;

        // use merging with exponential search
        do {
            java.lang.Comparable<Object> fromVal = (java.lang.Comparable<Object>) in[start];
            java.lang.Comparable<Object> rVal = (java.lang.Comparable<Object>) in[r];
            if (fromVal.compareTo(rVal) <= 0) {
                int l_1 = find(in, rVal, -1, start + 1, med - 1);
                int toCopy = l_1 - start + 1;
                System.arraycopy(in, start, out, i, toCopy);
                i += toCopy;
                out[i++] = rVal;
                r++;
                start = l_1 + 1;
            } else {
                int r_1 = find(in, fromVal, 0, r + 1, end - 1);
                int toCopy = r_1 - r + 1;
                System.arraycopy(in, r, out, i, toCopy);
                i += toCopy;
                out[i++] = fromVal;
                start++;
                r = r_1 + 1;
            }
        } while ((end - r) > 0 && (med - start) > 0);