Implementation of Merge Sort C++: cannot find mistake in my implementation

Question

Here is my implementation of Merge Sort:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std;


template <typename RandomIt>
void MergeSort(RandomIt range_begin, RandomIt range_end){

  int num_elements = distance(range_begin,range_end);
  if( num_elements < 2){
    return;
  }

  vector<typename RandomIt::value_type> v(range_begin, range_end);
  RandomIt mid_it = range_begin + num_elements/2;

  MergeSort(range_begin, mid_it);
  MergeSort(mid_it, range_end);

  for (int x : v) {
    cout << x << " ";
  }

  cout << endl;

  merge(begin(v), begin(v) + v.size()/2, begin(v) + v.size()/2, end(v), range_begin);


}

Important assumption: It is guaranteed that the length of the given range is a power of two, so the vector can always be divided into two equal parts.

When I execute int main() function I get the following:

int main() {
  vector<int> v = {6, 4, 7, 6, 4, 4, 0, 1};
  MergeSort(begin(v), end(v));
  for (int x : v) {
    cout << x << " ";
  }
  cout << endl;
  return 0;
}

result: 4 4 0 1 6 4 7 6

Sorting doesn't happen and algorithm basically swaps 2 halfs of the vector. I cannot find my mistake.

Have you tried to [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your program? For example by using a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through the code line by line while monitoring variables and their values. — Some programmer dude, Aug 24 '23 at 11:59
The fact that you think your code just swaps the two halves of the vector means you have not tested it much at all. — Nelfeal, Aug 24 '23 at 12:12
Hint: creating a vector at each step (or at all) is not desirable. — Nelfeal, Aug 24 '23 at 12:13
Did you expect the local `v` to become sorted by the recursive calls? — molbdnilo, Aug 24 '23 at 12:14
[How to implement classic sorting algorithms in modern C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). Compare your merge sort to the code at the link. — PaulMcKenzie, Aug 24 '23 at 13:24

Vlad from Moscow · Accepted Answer · 2023-08-24T12:38:54.367

Within the function there is declared a local vector

vector<typename RandomIt::value_type> v(range_begin, range_end);

that is not sorted. It is created anew in each recursive call of the function.

The only operation with this unsorted vector in the first recursive call of the function is the following

merge(begin(v), begin(v) + v.size()/2, begin(v) + v.size()/2, end(v), range_begin);

It means that the result content of the original vector is being built based on its original content using this operation in the first recursive call of the function. All subsequent recursive calls of the function do not influence on the content of the local vector declared in the first recursive call of the function.

The local vector v is redundant. In any case creating a new vector in each recursive call of the function makes the function inefficient. You need to use std::inplace_merge with the original vector within the function.

The function can look the following way

template <typename RandomIt>
void MergeSort( RandomIt range_begin, RandomIt range_end ) {

    auto num_elements = std::distance( range_begin, range_end );
    if ( notnum_elements < 2)
    {
        return;
    }

    RandomIt mid_it = std::next( range_begin, num_elements / 2 );

    MergeSort( range_begin, mid_it );
    MergeSort( mid_it, range_end );

    std::inplace_merge( range_begin, mid_it, range_end );
}

In this case the program output will be

0 1 4 4 4 6 6 7

Or if the compiler supports C++17 then the function can look the following way

template <typename RandomIt>
void MergeSort( RandomIt range_begin, RandomIt range_end ) 
{
    if ( auto num_elements = std::distance( range_begin, range_end ); not ( num_elements < 2 ))
    {
        RandomIt mid_it = std::next( range_begin, num_elements / 2 );

        MergeSort( range_begin, mid_it );
        MergeSort( mid_it, range_end );

        std::inplace_merge( range_begin, mid_it, range_end );
    }
}

score 0 · Answer 2 · answered Aug 24 '23 at 12:17

I found the following approach to be working

int range_length = distance(range_begin, range_end);
RandomIt mid = range_begin + range_length / 2;

vector<typename RandomIt::value_type> left(range_begin, mid);
vector<typename RandomIt::value_type> right(mid, range_end);

MergeSort(left.begin(), left.end());
MergeSort(right.begin(), right.end());

The problem with what you were doing was that when you merge the sorted halves of 'v' back into the original range, you're not actually modifying the original range. So, you are basically modifying the local vector 'v'. As a result, the sorted elements are stored in 'v', but the original range range_begin to range_end remains unchanged

Implementation of Merge Sort C++: cannot find mistake in my implementation

2 Answers2