Merge Sort Implementation using C++

Question

I am having trouble with trying to implement the merge sort algorithm. I would appreciate it if someone can help me out. Here is what I have.

#include <iostream>
#include <deque>
using size_type = std::deque<int>::size_type;
void print(std::deque<int> &v)
{
    for(const auto &ref:v)
        std::cout << ref << " ";
    std::cout << std::endl;
}
void merge(std::deque<int> &vec, size_type p, size_type q, size_type r)
{
    int n_1 = q - p;
    int n_2 = r - q;
    std::deque<int> left, right;
    for(auto i = 0; i != n_1; i++)
        left.push_back(vec[p + i]);
    for(auto j = 0; j != n_2; j++)
        right.push_back(vec[q + j]);
    int i = 0, j = 0;
    std::cout << "left = ";
    print(left);
    std::cout << "right = ";
    print(right);
    for(auto k = p; k != r; k++) {
        if(i < n_1 && left[i] <= right[j]) {
            vec[k] = left[i];
            i++;
        }
        else if(j < n_2){
            vec[k] = right[j];
            j++;
        }
    }
}
void merge_sort(std::deque<int> &A, size_type p, size_type r)
{
    int q;
    if(p < r) {
        q = (p + r)/2;
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}
int main()
{
    std::deque<int> small_vec = {1, 6, 2, 10, 5, 2, 12, 6};
    std::deque<int> samp_vec = {2, 9, 482, 72, 42, 3, 4, 9, 8, 73, 8, 0, 98, 72, 473, 72, 3, 4, 9, 7, 6, 5, 6953, 583};
    print(small_vec);
    merge_sort(small_vec, 0, small_vec.size());
    print(small_vec);
    return 0;
}

The output from the program is:

left = 
right = 1 
left = 1 
right = 6 
left = 
right = 10 
left = 1 6 
right = 2 10 
left = 
right = 2 
left = 
right = 6 
left = 2 
right = 12 6 
left = 1 2 6 10 
right = 5 2 12 6 
1 2 5 2 6 10 12 6

Hi. Asking people to spot errors in your code is not especially productive. You should use the debugger (or add print statements) to isolate the problem, by tracing the progress of your program, and comparing it to what you expect to happen. As soon as the two diverge, then you've found your problem. (And then if necessary, you should construct a minimal test-case.) — Oliver Charlesworth
– Oliver Charlesworth, Commented Sep 14, 2013 at 23:26

pippin1289 · Accepted Answer · 2013-09-15 00:24:02Z

1

There are a few issues with your sort. Firstly the merge step is wrong. Second how you call merge is wrong. Ill suggest a few steps to improve the implementation to a correct solution, and maybe itll help you.

First my code for merge:

void merge(std::deque<int> &vec, size_type p, size_type q, size_type r)
{
  std::deque<int> left, right;
  int i = p, j = q+1;
  while(i <= q) //change 1: to a while loop. expresses it a little simpler but 
                //you weren't inserting the correct left elements here
    left.push_back(vec[i++]);
  while(j <= r) //change 2: same thing, lets get the correct right values
    right.push_back(vec[j++]);
  i = 0; j = 0;
  for(auto k = p; k <= r; k++) {
    //change 3: alter this case to include the left over left elements! this is the main error
    if(i < left.size() && left[i] <= right[j] || j >= right.size())
        vec[k] = left[i++];
    else if(j < right.size())
        vec[k] = right[j++];
  }
}

Then to change how you call merge_sort to:

merge_sort(small_vec, 0, small_vec.size()-1); //change 4: initialized r wrong

This made the sort work for me. As a review of the problems I found: 1) not grabbing the correct subarrays of left and right. 2) didn't handle merge correctly - forgot to grab all the left elements after right is gone. 3) didn't call merg_sort correctly, initializing the r parameter incorrectly.

edited Sep 15, 2013 at 0:24

answered Sep 15, 2013 at 0:18

pippin1289

4,9492 gold badges25 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mars Over a year ago

Is there a way to call merge_sort using small_vec.size() and change the function itself to mimic calling it with small_vec.size() - 1?

pippin1289 Over a year ago

yes, there are a few ways, you can create a function merge_sort which alters this "r" value, calling merge_sort_impl which is actually what you already have written as "merge_sort"

Collectives™ on Stack Overflow

Merge Sort Implementation using C++

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related