我的合并排序实现哪里出错了？

Question

我正在学习排序算法并尝试实现 merge sort。我正在使用 C++ 编程语言。整个排序算法分为两个函数——mergeSort（将数组拆分为更小的部分）和 merge（合并已排序的数组）。请看下面我的代码

#include <iostream>
#include <vector>

void display(std::vector<int> arr)
{
  for (int i = 0; i < arr.size(); ++i)
    {
      std::cout << arr[i] << ' ';
    }
  std::cout << std::endl;
}

std::vector<int> merge(std::vector<int> arr, std::vector<int> left, std::vector<int> right)
{
  int k = 0, i = 0, j = 0;
  while ((i < left.size()) && (j < right.size()))
    {
      if (left[i] <= right[j])
    {
      arr[k] = left[i];
      ++i;
    }
      else if (left[i] > right[j])
    {
      arr[k] = right[j];
      ++j;
    }
      ++k;
    }
  while (i < left.size())
    {
      arr[k] = left[i];
      ++i;
      ++k;
    }
  while (j < right.size())
    {
      arr[k] = right[j];
      ++j;
      ++k;
    }
  return arr;
}

std::vector<int> mergeSort(std::vector<int> arr)
{
  if (arr.size() < 2) return arr;
  int mid = arr.size() / 2;
  std::vector<int> left{};
  std::vector<int> right{};
  for (int i = 0; i < mid; ++i)
    {
      left.push_back(arr[i]);
    }
  for (int j = mid; j < arr.size(); ++j)
    {
      right.push_back(arr[j]);
    }
  left = mergeSort(left);
  right = mergeSort(right);
  merge(arr, left, right);
  return arr;
}

int main()
{
  std::vector<int> arr{6,2,3,1,9,10,15,13,12,17};
  display(mergeSort(arr));
  return 0;
}

我的代码无法正常工作，例如它 returns

6 2 3 1 9 10 15 13 12 17

当我尝试排序时

6 2 3 1 9 10 15 13 12 17

但是我找不到我的错误。如果有人指出，我将不胜感激。

Answer 1

您在 mergeSort 中的 merge(arr, left, right) 调用实际上并未将 left 和 right 合并到 arr 中。它 returns 一个新数组代替。相反，写：

arr = merge(arr, left, right);

我的合并排序实现哪里出错了？

Where is mistake in my Merge Sort implementation?

c++

sorting

mergesort