recursion - Recursive mergeSort to Iterative in c++ using deque -

i'm trying iterative version of multiple recursive mergesort:

i need make iterable 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 = 0; < middle; i++){     left.push_back(right.front());     right.pop_front();   }   left = sort(left);   right = sort(right);   return merge(left, right); } 

the merge function can 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 me make tranformation of multiple recursive function iterative function.

thanks everyvody , kind regards.

do have use dequeue? iterative version of merge sort called bottom-up merge sort. there's no need store information.