/**
 * 针对整形的排序实现
 * @param x 待排序的数据
 * @param off 起始位置
 * @param len 要排序的数据元素的个数
 */
private static void sort1(int x[], int off, int len) {
    //在小规模(size<7)数组中，直接插入排序的效率要比快速排序高。
    if (len < 7) {
        for (int i=off; i<len+off; i++)
            for (int j=i; j>off && x[j-1]>x[j]; j--)
                swap(x, j, j-1);
        return;
    }

    //选择划分元素，即枢轴
    //如果是小规模数组(size=7)，直接取中间元素作为枢轴
    //如果是中等规模数组(7<size<=40)，则在数组首、中、尾三个位置上的数中取中间大小的数作为枢轴
    //如果是大规模数组(size>40),则在9个指定的数中取一个伪中数(中间大小的数s)
    int m = off + (len >> 1);
    if (len > 7) {
        int l = off;
        int n = off + len - 1;
        if (len > 40) {        // Big arrays, pseudomedian of 9
            int s = len/8;
            l = med3(x, l,     l+s, l+2*s);
            m = med3(x, m-s,   m,   m+s);
            n = med3(x, n-2*s, n-s, n);
        }
        m = med3(x, l, m, n); // Mid-size, med of 3
    }
    int v = x[m];

    // 针对相同的元素做优化， 形成 v* (<v)* (>v)* v* 的数组
    int a = off, b = a, c = off + len - 1, d = c;
    while(true) {
        while (b <= c && x[b] <= v) {
            if (x[b] == v)
                swap(x, a++, b);
            b++;
        }
        while (c >= b && x[c] >= v) {
            if (x[c] == v)
                swap(x, c, d--);
            c--;
        }
        if (b > c)
            break;
        swap(x, b++, c--);
    }

    // 将所有相同的枢轴都移到中间，形成(<v)* v* (>v)*
    int s, n = off + len;
    s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
    s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

    // 递归排序子数组
    if ((s = b-a) > 1)
        sort1(x, off, s);
    if ((s = d-c) > 1)
        sort1(x, n-s, s);
}

/**
 * 归并排序对象数组
 * @param src 原待排数组
 * @param dest 目的待排数组
 * @param low 待排数组的下界位置
 * @param high 待排数组的上界位置
 * @param off 从数组的第off个元素开始排序
 */
private static void mergeSort(Object[] src,
                              Object[] dest,
                              int low,
                              int high,
                              int off) {
    int length = high - low;

    //在小规模(size<7)数组中，使用归并排序。
    if (length < INSERTIONSORT_THRESHOLD) {
        for (int i=low; i<high; i++)
            for (int j=i; j>low &&
                    ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                swap(dest, j, j-1);
        return;
    }

    //将src数组划分为两半，并分别递归做归并，
    //在递归调用mergeSort时将desc和src的位置做了互换。
    int destLow  = low;
    int destHigh = high;
    low  += off;
    high += off;
    int mid = (low + high) >>> 1;
    mergeSort(dest, src, low, mid, -off);
    mergeSort(dest, src, mid, high, -off);

    //如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并
    //如果需要归并的两端low~(middle-1)，middle~high已经有序，即src[mid-1]==src[mid]。
    //那么只需要将src的low~high赋值对应的dest即可，无需再归并。
    if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
        System.arraycopy(src, low, dest, destLow, length);
        return;
    }

    //将src的两个部分做归并操作，并赋值给dest
    for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
        if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
            dest[i] = src[p++];
        else
            dest[i] = src[q++];
    }
}