replace this vector to array void merge_sort_4(vector lst,int start,int end){ if (start < end){ int quarter1 = (start + end) / 4; int quarter2 = (start + end) / 2; int quarter3 = (end - quarter1 - 1); merge_sort_4(lst, start, quarter1); merge_sort_4(lst, quarter1 + 1, quarter2); merge_sort_4(lst, quarter2 + 1, quarter3); merge_sort_4(lst, quarter3 + 1, end); merge4(lst, start, quarter1, quarter2, quarter3, end); } } void merge4(vector lst,int start,int q1,int q2,int q3,int end){ vector first_q_list; for(int i=start;i sec_q_list; for(int i=q1+1;i third_q_list; for(int i=q2+1;i last_q_list; for(int i=q1+1;i
this function c++ accept
replace this vector to array
void merge_sort_4(vector<int> lst,int start,int end){
if (start < end){
int quarter1 = (start + end) / 4;
int quarter2 = (start + end) / 2;
int quarter3 = (end - quarter1 - 1);
merge_sort_4(lst, start, quarter1);
merge_sort_4(lst, quarter1 + 1, quarter2);
merge_sort_4(lst, quarter2 + 1, quarter3);
merge_sort_4(lst, quarter3 + 1, end);
merge4(lst, start, quarter1, quarter2, quarter3, end);
}
}
void merge4(vector<int> lst,int start,int q1,int q2,int q3,int end){
vector<int> first_q_list;
for(int i=start;i<q1+1;i++)
first_q_list.push_back(lst[i]);
vector<int> sec_q_list;
for(int i=q1+1;i<q2+1;i++)
sec_q_list.push_back(lst[i]);
vector<int> third_q_list;
for(int i=q2+1;i<q3+1;i++)
third_q_list.push_back(lst[i]);
vector<int> last_q_list;
for(int i=q1+1;i<end+1;i++)
last_q_list.push_back(lst[i]);
int INF=INT_MAX;
first_q_list.push_back(INF);
sec_q_list.push_back(INF);
third_q_list.push_back(INF);
last_q_list.push_back(INF);
int i = 0; // first sublist index
int j = 0; // sec sublist index
int m = 0; // third sublist index
int n = 0; // last sublist index
for(int i=start;i<end+1;i++){
if (first_q_list[i] <= sec_q_list[j] and first_q_list[i] <= third_q_list[m] and first_q_list[i] <= last_q_list[n]){
lst[k] = first_q_list[i];
i += 1;
}
else if (sec_q_list[j] <= third_q_list[m] and sec_q_list[j] <= last_q_list[n]){
lst[k] = sec_q_list[j];
j += 1;
}
else if (third_q_list[m] <= last_q_list[n]){
lst[k] = third_q_list[m];
m += 1;
}
else{
lst[k] = last_q_list[n];
n += 1;
}
}
}
Step by step
Solved in 3 steps with 3 images