Where is mistake in my Merge Sort implementation?

Question

I'm learning sorting algorithms and trying to implement merge sort. I'm using the C++ programming language. The entire sorting algorithm is splitted into two functions -- mergeSort (splitting an array into smaller pieces) and merge (merging already sorted arrays). Please take a look on my code below

#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;
}

My code isn't working properly, e.g. it returns

6 2 3 1 9 10 15 13 12 17

when I'm trying to sort

6 2 3 1 9 10 15 13 12 17

however I can't find my mistake. I would be very grateful if someone will point it out.

Answer 1

Your merge(arr, left, right) call in mergeSort doesn't actually merge left and right into arr. It returns a new array instead. Instead, write:

arr = merge(arr, left, right);