Java 位图法排序的使用方法

/**
     * 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 performed by linear search.
     *
     * @param in –
     *            the array for sorting.
     * @param out –
     *            the result, sorted array.
     * @param start
     *            the start index
     * @param end
     *            the end index + 1
     */
    @SuppressWarnings(“unchecked”)
    private static void mergeSort(Object[] in, Object[] out, int start,
            int end) {
        int len = end – start;
        // use insertion sort for small arrays
        if (len <= SIMPLE_LENGTH) {
            for (int i = start + 1; i <end; i++) {
                Comparable current = (Comparable) 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 (((Comparable) 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 {
            Comparable fromVal = (Comparable) in[start];
            Comparable rVal = (Comparable) 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 来源gao@!dai!ma.com搞$$代^@码网= 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);

        // copy rest of array
        if ((end – r) <= 0) {
            System.arraycopy(in, start, out, i, med – start);
        } else {
            System.arraycopy(in, r, out, i, end – r);
        }
    }