2
\$\begingroup\$

I am currently reading an algorithms book and I read on the insertion and merge sorts. I implemented the merge sort in C++, The first function MERGE is responsible for the merging of the two subarrays part and the function MERGE_SORT is the actual algorithm. I am interested to know whether or not my code has a good readability factor and if It can be optimized further or not?

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

#define itr vector<int>::iterator
void MERGE(vector<int>& vec,itr left, itr mid, itr right){
    //Make vector left with elements from left to mid inclusive
    vector<int> left_vec;
    for (itr i=left; i!=vec.end()&&i<=mid;i++){
        left_vec.push_back(*i);
    }
    left_vec.push_back(numeric_limits<int>::max());//sentinel card
    //make vector right with elements from mid+1 to right inclusive
    vector<int> right_vec;
    for (itr i=mid+1; i!=vec.end() && i<=right; i++){
        right_vec.push_back(*i);
    }
    right_vec.push_back(numeric_limits<int>::max());//sentinel card
    //Now add them in a sorted manner to vector from left to right

    itr l=left_vec.begin(); itr r=right_vec.begin();
    for (itr vec_itr=left;vec_itr!=vec.end()&&vec_itr<=right;vec_itr++){
        if (*l<=*r){
            *vec_itr=*l;
            l++;
        }
        else{
            *vec_itr = *r;
            r++;
        }
    }
}
void MERGE_SORT(vector<int>& vec, itr left, itr right){
    if(left<right){
        itr mid = left + (right-left)/2;
        MERGE_SORT(vec,left,mid);
        MERGE_SORT(vec,mid+1,right);
        MERGE(vec, left,mid,right);
    }
    return;
}
int main() {
    int a[] = {10,8,9,7,6,3,3,9,15,4,3,2,1};
    vector<int> vec(a,a+13);
    MERGE_SORT(vec,vec.begin(),vec.end());
    for (itr i=vec.begin();i!=vec.end();i++)cout << *i << " ";
    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

First off, I'd use typedef rather than #define.

You don't really need to reference vec.end(); you know mid <= right <= vec.end() and the fact that you're copying the same number of elements back in as you copied out, means you don't need to compare vec_itr to vec.end(). What this really means is that you don't need the vec parameter to MERGE.

vector<T> has a constructor that copies from an iterator. Your push_back for loop could be simplified to

vector<int> left_vec(left, mid);
vector<int> right_vec(mid, right);

The push_back of max() as a sentinel is not strictly needed. Instead, you can just loop until you hit the end of either left_vec or right_vec and then copy the remainder of the vectors to the left to right range.

Your variable names might be easier to understand.

typedef itr vector<int>::iterator;

void MERGE(itr left, itr mid, itr right){
    //Make vector left with elements from left to mid-1 inclusive
    vector<int> left(left, mid);

    //make vector right with elements from mid to right-1 inclusive
    vector<int> right(mid, right);

    // Now concurrently loop over the left and right vectors
    // and add the values back to left to right. Stop when 
    // either iterator runs out of elements.
    itr left_src=left.begin();
    itr right_src=right.begin();
    itr dest = left;
    while (left_src != left.end() && right_src != right.end()) {
        // pick the iterator with the smallest current value
        itr& least_src = (*left_src < *right_src) ? left_src : right_src;
        *dest = *least_src;
        least_src ++;
        dest ++;
    }

    // copy remainder of left (maybe 0 elements)
    copy(left_src, left.end(), dest);

    // copy remainder of right (maybe 0 elements)
    copy(right_src, right.end(), dest);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.