向量大小非2^n时归并排序函数失效问题排查

你的代码在处理非2^n大小的数组时出错，核心问题出在子数组遍历完成的判断逻辑以及合并阶段的条件执行顺序：

问题1：错误使用原数组的ceil/floor值判断子数组是否遍历完毕 #

你在合并时用counter1 == ceil(vsize / 2)和counter2 == floor(vsize / 2)来判断子数组是否处理完，但这两个值并不等于子数组的真实大小：

• 当原数组大小为奇数（比如3），vsize / 2是整数除法，结果为1，ceil(1)仍为1，此时halfv1大小为1，halfv2大小为2，但floor(vsize/2)是1，和halfv2.size()完全不符；
• 当counter2达到1时，代码错误认为halfv2已遍历完毕，强行填充halfv1的剩余元素，但halfv1此时已无剩余元素，导致越界访问，最终输出错误值。

另外，ceil(vsize / 2)的整数除法会导致分割逻辑失效：因为vsize和2都是int类型，奇数大小的数组（如3）会被计算为3/2=1，ceil(1)还是1，无法将数组按预期分成2和1的两个子数组。

问题2：合并阶段的条件未用else if串联，导致多条件触发 #

三个if是顺序执行的，即使第一个条件已经完成所有元素的填充，后面的条件仍然会执行，可能引发重复操作或越界。

修复方案 #

基于你的现有代码逻辑，仅需修改以下几点：

1. 用子数组的size()替代原数组的ceil/floor计算值，作为遍历完成的判断依据；
2. 将合并阶段的三个if改为if-else if-else结构，避免多条件同时触发；
3. 将ceil(vsize / 2)改为ceil(vsize / 2.0)，确保是浮点数除法，正确分割奇数大小的数组。

修改后的完整代码：

#include <bits/stdc++.h>
using namespace std;

vector<int> mergesort(vector <int> x);
int main(){
    vector<int> tosort={1,9,0};
    tosort=mergesort(tosort);
    for(int  i=0; i<tosort.size(); i++){
        cout<<tosort[i]<<" ";
    }

}
vector<int> mergesort(vector <int> x){
   if (x.size()==1){
       return x ;
   }
   else{
       int vsize=x.size();
       vector<int> halfv1(x.begin(),x.begin()+ceil(vsize / 2.0));
       vector<int> halfv2(x.begin()+ceil(vsize / 2.0),x.end());
       
       halfv1=mergesort(halfv1);
       halfv2=mergesort(halfv2);
       int counter1=0;
       int counter2=0;
       while(counter1+counter2 < vsize){
           if(counter1 == halfv1.size()){
               for(int i=counter1+counter2;i<vsize;i++){
                   x[i]=halfv2[counter2];
                   counter2++;
               }
           }
           else if(counter2 == halfv2.size()){
               for(int i=counter1+counter2;i<vsize;i++){
                   x[i]=halfv1[counter1];
                   counter1++;
               }
           }
           else{
               if(halfv1[counter1] <= halfv2[counter2]){
                   x[counter1+counter2]=halfv1[counter1];
                   counter1++;
               }
               else{
                   x[counter1+counter2]=halfv2[counter2];
                   counter2++;
               }
           }
       }
       return x;
   }
}

测试输入{1,9,0}，修改后的代码会输出0 1 9，符合预期。

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