数组严格二分分区实现疑问：左半全小于右半的代码问题排查

需求描述 #

将数组A[n]基于中间值midval划分为两个子数组A1（左半部分）与A2（右半部分），要求A1的所有元素均小于midval，A2的所有元素均大于midval。

实现问题 #

参考某论文第一分区阶段实现了如下代码，但无法严格实现左半部分元素全小于右半部分的效果。

代码实现 #

int pivot = data.Length / 2;

// 计算左右两部分的最大、最小值
int Lmax = int.MinValue, Lmin = int.MaxValue, Rmax = int.MinValue, Rmin = int.MaxValue;
for (int i = 0; i < pivot; i++)
{
    if (data[i] > Lmax)
        Lmax = data[i];
    if (data[i] < Lmin)
        Lmin = data[i];
}
for (int i = pivot; i < data.Length; i++)
{
    if (data[i] > Rmax)
        Rmax = data[i];
    if (data[i] < Rmin)
        Rmin = data[i];
}

// 计算中间值midval
int midval = (Lmax + Lmin + Rmax + Rmin) / 4;

// 执行交换操作
for (int i = 0, j = data.Length - 1; i < pivot && j >= pivot;)
{

    if (data[i] >= midval && data[j] < midval)
    {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
        i++;
        j--;
    }
    else if(data[i] < midval)
    {
        i++;
    }
    else if(data[j] >= midval)
    {
        j--;
    }
}

代码逻辑说明 #

• 以数组长度的一半作为分界点pivot，将数组划分为左右两部分
• 分别统计左半部分的最大值Lmax、最小值Lmin，右半部分的最大值Rmax、最小值Rmin
• 通过四个值的平均值计算得到midval
• 使用双指针交换左半部分中大于等于midval的元素，与右半部分中小于midval的元素

当前问题与疑问 #

交换过程会因指针触达pivot范围提前终止，导致中间存在未检查的元素，最终无法严格满足“左半部分所有元素均小于右半部分”的要求。怀疑midval的计算公式有误，请问这个判断是否正确？

内容的提问来源于stack exchange，提问作者Gregster