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 <iostream>
#include <thread>
#include <cstdlib>
#include <vector>
#define NUM 1048576*2
int sort(std::vector<int>* vec);
void run(std::vector<int>* vec, int left, int right);
void merge(std::vector<int>* vec, int left, int mid, int right);
int main() {
srand(time(NULL));
std::vector<int> tobesorted;
for(int i = 0; i < NUM; i++){
tobesorted.push_back(rand());
}
sort(&tobesorted);
for(int i = 0; i < NUM; i++){
std::cout << tobesorted[i] << ", ";
}
std::cout << std::endl;
std::cout << "End of Program!";
}
int sort(std::vector<int>* pvec){
int size = pvec->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<int>* 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<int>* pvec, int left, int mid, int right){
int ileft = 0;
int iright = 0;
int index = 0;
std::vector<int> leftvec;
std::vector<int> rightvec;
int j = 0;
for(int i= left; i <= mid; i++){
leftvec.push_back(pvec[0][i]);
}
j = 0;
for(int i= mid+1; i <= right; i++){
rightvec.push_back(pvec[0][i]);
}
while(ileft < leftvec.size() && iright < rightvec.size()){
if(leftvec[ileft] > rightvec[iright]){
pvec[0][left+index] = leftvec[ileft++];
index++;
} else {
pvec[0][left+index] = rightvec[iright++];
index++;
}
}
while(ileft < leftvec.size()){
pvec[0][left+index] = leftvec[ileft++];
index++;
}
while(iright < 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?
std::thread t1(run, vec, left, right);
is thatthread
's constructor makes thread-local copies of things by default. (That's the conservative, thread-safe choice.) If you really want references, the trick is to dostd::thread t1(run, std::ref(vec), left, right);
. \$\endgroup\$