I implemented Merge sort in C++
vector<int> merge(vector<int> &p, vector<int> &q){
vector<int> ans;
int pi = 0,qj = 0;
while (pi < p.size() && qj < q.size()) {
if (p[pi] <= q[qj]) {
ans.push_back(p[pi]);
pi++;
} else{
ans.push_back(q[qj]);
qj++;
}
}
if (pi == p.size()) {
while (qj < q.size()) {
ans.push_back(q[qj]);
qj++;
}
}
else {
ans.push_back(p[pi]);
pi++;
}
return ans;
}
vector<int> mSort(vector<int> &ip, unsigned long long n) {
if (n==1) {
return ip;
}
unsigned long long mid = (n/2);
vector<int> p;
for (int i = 0; i < mid; i++) {
p.push_back(ip[i]);
}
p = mSort(p, p.size());
vector<int> q;
for (int i = mid; i < n; i++) {
q.push_back(ip[i]);
}
q = mSort(q, q.size());
vector<int> ans = merge(p, q);
return ans;
}
// Call function as
vector<int> ans = mSort(ipArray, ipArray.size())
//
Comments
Post a Comment