C++ Merge Sort Algorithm I have created this first-timer implementation of Merge Sort
and I got confused by the C++ syntax once or twice.

So I have some questions about this code:

#include &lt;iostream&gt;
#include &lt;thread&gt;
#include &lt;cstdlib&gt;
#include &lt;vector&gt;

#define NUM 1048576*2

int sort(std::vector&lt;int&gt;* vec);
void run(std::vector&lt;int&gt;* vec, int left, int right);
void merge(std::vector&lt;int&gt;* vec, int left, int mid, int right);

int main() {
    srand(time(NULL));
    std::vector&lt;int&gt; tobesorted;
    for(int i = 0; i &lt; NUM; i++){
        tobesorted.push_back(rand());
    }

    sort(&amp;tobesorted);

    for(int i = 0; i &lt; NUM; i++){
        std::cout &lt;&lt; tobesorted[i] &lt;&lt; ", ";
    }
    std::cout &lt;&lt; std::endl;
    std::cout &lt;&lt; "End of Program!";


}
int sort(std::vector&lt;int&gt;* pvec){
    int size = pvec-&gt;size();
    std::thread t1(run, pvec, 0, 0.25*size);
    std::thread t2(run, pvec, 0.25*size+1, 0.5*size);
    std::thread t3(run, pvec, 0.5*size+1, 0.75*size);
    std::thread t4(run, pvec, 0.75*size, size-1);

    t1.join();
    t2.join();
    t3.join();
    t4.join();

    std::thread t5(merge, pvec, 0, 0.25*size, 0.5*size);
    merge(pvec, 0.5*size+1, 0.75*size, size-1);
    t5.join();

    merge(pvec, 0, 0.5*size, size-1);

    return 1;
}

void run(std::vector&lt;int&gt;* pvec, int left, int right){
    if(right - left == 0){
        return;
    }
    int mid = (left+ right)/2;
    run(pvec, left,mid);
    run(pvec, mid+1, right);

    merge(pvec, left, mid, right);

}

void merge(std::vector&lt;int&gt;* pvec, int left, int mid, int right){
    int ileft = 0;
    int iright = 0;
    int index = 0;


    std::vector&lt;int&gt; leftvec;
    std::vector&lt;int&gt; rightvec;

    int j = 0;
    for(int i= left; i &lt;= mid; i++){
        leftvec.push_back(pvec[0][i]);
    }
    j = 0;
    for(int i= mid+1; i &lt;= right; i++){
        rightvec.push_back(pvec[0][i]);
    }

    while(ileft &lt; leftvec.size() &amp;&amp; iright &lt; rightvec.size()){
        if(leftvec[ileft] &gt; rightvec[iright]){
            pvec[0][left+index] = leftvec[ileft++];
            index++;
        } else {
            pvec[0][left+index] = rightvec[iright++];
            index++;
        }
    }

    while(ileft &lt; leftvec.size()){
        pvec[0][left+index] = leftvec[ileft++];
        index++;
    }

    while(iright &lt; rightvec.size()){
        pvec[0][left+index] = rightvec[iright++];
        index++;
    }

}



I think I should have better optimized for better cache use, do you see any opportunities there?
What could have been generally improved on that code?
This code doesn't work, as can be shown by including &lt;algorithm&gt; and changing the output:

std::cout &lt;&lt; std::is_sorted(tobesorted.begin(), tobesorted.end()) &lt;&lt; std::endl;




Other things that are surprising:


We pass pointers but always assume they are not null.  That suggests we should be using references instead.
Misspelt std::srand and std::time - though I'd recommend using &lt;random&gt; instead.
std::endl used where there's no need to flush output - just write \n instead.
Why are we using int rather than std::size_t for our left and right indices?
Use of floating-point multiplication for integer arithmetic.
Unused variable j.




There's a risk of overflow here:


int mid = (left+ right)/2;



Better would be

auto mid = left + (right - left) / 2;




This code can be re-written:


std::vector&lt;int&gt; leftvec;
std::vector&lt;int&gt; rightvec;

for(int i= left; i &lt;= mid; i++){
    leftvec.push_back(pvec[0][i]);
}
for(int i= mid+1; i &lt;= right; i++){
    rightvec.push_back(pvec[0][i]);
}



Those vectors will likely re-allocate several times as they are filled, because we didn't reserve() capacity.  Instead of those loops, we could use the appropriate constructor:

std::vector&lt;int&gt; leftvec(pvec-&gt;begin()+left, pvec-&gt;begin()+mid);
std::vector&lt;int&gt; rightvec(pvec-&gt;begin()+mid, pvec-&gt;&gt;begin()+right+1);


It would be easier if we passed iterators rather than indices here.