private static int partitionMethodC(long[] array, int from, int to) {
        int s = from;
        long pivot = array[to];
        for (int i = from; i < to; i++) {   // 遍历 [from, to)
            // 这里加 == 号也保证不了稳定性，有交换操作
            if (array[i] < pivot) {
                // TODO: 可以进行简单的优化：如果 i == s，就不交换
                long t = array[i];
                array[i] = array[s];
                array[s] = t;
                s++;
            }
        }
        array[to] = array[s];
        array[s] = pivot;
        return s;
    }

private static void merge(long[] array, int from, int mid, int to) {
        // 先计算出来额外空间需要多个，计算两个区间加起来多少个元素
        int size = to - from;
        // 申请一个额外的数组作为临时保存的地方
        long[] other = new long[size];  // 需要一个 和 n 长度一致的空间
        int left = from;    // 左边小区间的下标
        int right = mid;    // 右边小区间的下标
        int dest = 0;       // 临时空间的下标
        // 只要左右两个小区间还有元素要参与比较
        while (left < mid && right < to) {
            if (array[left] <= array[right]) {
                other[dest++] = array[left++];
            } else {
                other[dest++] = array[right++];
            }
        }
        // 其中一个区间的元素取完了，另一个区间里一定还有元素，再把剩余的元素，统统放入 other
        // 看起来左右两个都写了，但执行起来的时候一定只有一个会执行
        while (left < mid) {
            other[dest++] = array[left++];
        }
        while (right < to) {
            other[dest++] = array[right++];
        }
        // 把 other 中的有序元素，复制回 array 中，要注意下标的问题
        for (int i = 0; i < size; i++) {
            array[from + i] = other[i];     // array 下标的基准是从 [from] 开始，other 下标的基准是从 [0] 开始
                                            // offset(偏移）是一致的，都是 i
        }
    }