c++ - 合并排序 C++ 实现，无法识别代码中的错误

Question

我尝试使用 std::vector 在 C++ 中实现归并排序。我看不出逻辑上有什么问题。但是，当我运行代码时，我得到一个比原始数组大且未排序的数组。谁能告诉我我的代码有什么问题？

void  merge(vector<double>& x,
            vector<double>& y,
            vector<double>& merged )
{
   int sze_x = x.size();
   int sze_y = y.size();
   int i =0, j=0;

   while (i< sze_x && j < sze_y)
   {
      if(x[i] <= y[j])
      {
         merged.push_back(x[i]);
         ++i;
      }
      else
      {
         merged.push_back(y[j]);
         ++j;

      }
   }
   if(i >= sze_x)
   {
      for(int l =j; l != sze_y; l++)
      {
         merged.push_back(y[l]);

      }
   }
   else
   {
      for(int l =i; l != sze_x; l++)
      {
         merged.push_back(x[l]);
      }
   }

}

void split (vector<double> &A, vector<double> &A_1, vector<double> &A_2)
{
   int mid = A.size()/2;
   int sze = A.size();
   for(int i =0; i!=sze;i++)
   {
      if(i<mid) A_1.push_back(A[i]);
      else
         A_2.push_back(A[i]);
   }
}

void merge_sort(vector<double>  &arr)
{
   if(arr.size()>1)
   {
      vector<double> arr1, arr2;
      split(arr,arr1,arr2);
      merge_sort(arr1);
      merge_sort(arr2);
      merge(arr1,arr2,arr);

   }
}

Answer 1

当你打电话时

 merge(arr1,arr2,arr);

arr 仍然保留其所有原始内容。在 merge 中调用 push_back 到 merged 之前，您没有清除内容。

添加

arr.clear();

在上面一行之前，或者添加

merged.clear();

在 while 语句之前的 merge 中。

merged.clear();
while (i< sze_x && j < sze_y)