Do you have to use dequeue? The iterative version of merge sort is called a bottom-up merge sort. There's really no need to store extra information.
Recursive mergeSort to Iterative in c++ using deque
Question
I'm trying to do the iterative version of this multiple recursive mergesort:
I only need to make iterable this sort function:
template<class T> deque<T> mergesort<T>::sort(deque<T> &right){
int size = right.size();
if (size <= 1){
return right;
}
int middle = size/2;
deque<T> left;
for(int i = 0; i < middle; i++){
left.push_back(right.front());
right.pop_front();
}
left = sort(left);
right = sort(right);
return merge(left, right);
}
The merge function can be the same:
template<class T> deque<T> mergesort<T>::merge(deque<T> &left, deque<T> &right){
deque<T> result;
while(left.size() > 0 || right.size() > 0){
if (left.size() > 0 && right.size() > 0){
if (getOrder(left.front(),right.front())){
result.push_back(left.front());
left.pop_front();
}
else{
result.push_back(right.front());
right.pop_front();
}
}
else if(left.size() > 0){
result.push_back(left.front());
left.pop_front();
}
else if(right.size() > 0){
result.push_back(right.front());
right.pop_front();
}
}
return result;
}
It's hard for me to make the tranformation of multiple recursive function to iterative function.
Thanks everyvody and kind regards.
Solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow