C++ Implementing Mergesort with vectors

Question

I am using C++ to implement the mergesort algorithm using vectors instead of arrays. I worked step by step from the original algorithm but when I compile, I get no output or error messages. I think there is an issue with my "merge" function but I cannot find it. I am new to sorting algorithms so if there are any fundamental misunderstandings or errors in my code please explain them to me.

#include <iostream>
#include <vector>
using namespace std;

void mergeSort(vector<int>& numvec, int left, int right){

    if(left < right){
        int middle = left + (right - left) / 2;

    mergeSort(numvec, left, middle);
    mergeSort(numvec, middle + 1, right);
    merge(numvec, left, middle, right);
    }
}

int merge(vector<int>& numvec , int left, int mid, int right){

    int i, j, k, temp[right-left+1];

    i = left;
    j = right;
    k = mid + 1;

    while(i <= mid && j <= right){

        if(numvec[i] < numvec[j])
     {
        temp[k] = numvec[i];
        k++;
        i++;
    }
    else
    {
        temp[k] = numvec[j];
        k++;
        j++;
    }
    while(i <= mid){

        temp[k] = numvec[i];
        k++;
        i++;
    }   
    while( j <= right){
        temp[k] = numvec[j];
    }
    for(i = left; i <= right; i++){
        numvec[i] = temp[i - left];
    }
    }
}

please provide a [mre], also note that variable size stack allocated arrays are a non-standard gcc extension, you should use a `vector` instead — Alan Birtles, Sep 29 '19 at 16:10
`temp[right-left+1]` -- You are already using `vector`. You should be using it here also. You should understand why `std::vector` exists, and it is for this purpose (dynamic arrays). — PaulMcKenzie, Sep 29 '19 at 16:16
I didn't go through in detail but you definitely need to start counting `k` from 0, not from `mid+1` — mangusta, Sep 29 '19 at 16:16
see also: https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c — Caleth, Jul 01 '20 at 17:50

Ayush Jain · Answer 1 · 2020-07-01T18:08:51.087

The mistakes I can find till now in the code is given below :

int merge(vector<int>& numvec , int left, int mid, int right)

When you are merging both left and right vectors you will have to return the merged vector instead of int.
k = mid + 1

k will start from l instead of mid + 1 because at any level we will start filling elements from the first index of left vector not from the first element of right vector which is mid + 1.
Also, you will need to declare two vectors to store elements from left to mid in one vector and mid+1 to right in another.

Now, If you have to implement Merge Sort strictly using vector then you can see my code.

 vector<int> merge(vector<int> l,vector<int> r)
    {

   vector<int> res;
        
        int i=0;
        int j=0;
        while(i!=l.size() && j!=r.size())
        {
            if(l[i]<=r[j])
            {
                re.push_back(l[i++]);
            }
            else
            {
                re.push_back(r[j++]);
            }
        }
        
        while(i!=l.size())
            re.push_back(l[i++]);
        
        while(j!=r.size())
            re.push_back(r[j++]);
        
        return res;
    }
    
    
    vector<int> merge_d(vector<int>&A, int s,int e)
    {
        if(s-e==0)
        {
            vector<int> t;
            t.push_back(A[s]);
            return t;
        }
    
        int m=(s+e)/2;
        
        vector<int> l;
        vector<int> r;
        l=merge_d(A,s,m);
        r=merge_d(A,m+1,e);
        
        return merge(l,r);
    }

score 0 · Answer 2 · answered Jul 01 '20 at 17:47

The first problem is in the code below:

int merge(vector<int>& numvec , int left, int mid, int right)

You said you will return an integer but never returned anything. Also for mergeSort, you are supposed to declare two temp arrays, one for the right side and one for the left side so you can merge them, but you never did. Finally the code below makes no sense at all:

for(i = left; i <= right; i++){
        numvec[i] = temp[i - left];
    }

It looks like black box, that just magically came from nowhere and has nothing to do with mergeSort whatsoever, if you want to improve other's code please make sure you understand the algoritm first.

C++ Implementing Mergesort with vectors

2 Answers2