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>::iteratorvoid 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;}
Recursive Implementation of Merge Sort C++
c++;performance;recursion;mergesort
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 tovector<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);}