Sorting Algorithm - java sorting stacks

It's possible to implement a bottom up merge sort O(n log(n)) using queue and stack. First, all elements are popped from the stack onto the queue (this reverses elements). Queue will be sorted in reverse (reverse the sense of the compare). The first merge pass pops one element from the queue and pushes it onto stack, compares queue.front() with stack.top(), pops and pushes the smaller onto queue, then pops and pushes the other, repeating until all pairs of elements are merged, creating sorted runs of size of 2 in queue. Then to setup for next pass, queue is cycled to reverse all even runs (except if there's a lone even run at the end with no odd run to merge with, in which case it's just copied and not reversed): even runs from queue are pushed onto stack, then popped from stack and pushed onto queue to reverse them, odd runs are popped from queue and pushed onto queue to copy them in order. For the remaining passes, pairs of runs are merged by popping an even run from queue and pushing it onto stack, "unreversing" it on stack, then the even run at stack.top() is merged with the odd run at queue.front(), pushing the merged runs back onto queue. Once all pairs are merged, run size is doubled and if run size < queue.size(), then queue is cycled again to reverse all even runs and the merge process repeated; else run size >= queue.size() and queue is sorted (in reverse). The reverse sorted queue is popped and pushed onto stack creating a sorted stack.

I tried to figure out a way to reverse the sense of the compare during a merge to avoid having to do a reverse even runs cycle after each merge pass, but it's a recursive pattern, that I couldn't figure out how to replicate with iteration. The simpler reverse even runs approach seems fast enough anyway.

On my system, Intel 2600K 3.4 ghz, Visual Studio release build, this method can sort 4 million psuedo random 32 bit unsigned integers in about 2.8 seconds.

Example code for ascending sort of stack (reverse sense of compare for descending) . ll, rr, and ee are pseudo indexes to keep the run count logic the same as an array / vector bottom up merge sort. The actual merge uses stack for the left / even run, and a part of queue for the right / odd run.

typedef unsigned int uint32_t;

void sqsort(std::stack <uint32_t> &s , std::queue <uint32_t> &q)
{
    size_t n = s.size();
    while(!s.empty()){                      // pop/push s to q
        q.push(s.top());
        s.pop();
    }
    // merge sort usign stack and queue
    size_t r = 1;
    while(1){
        size_t ee = 0;                      // pseudo end index
        // merge pass
        while(ee < n){
            size_t ll = ee;                 // ll = pseudo start of left  run
            size_t rr = ll+r;               // rr = pseudo start of right run
            if(rr >= n){                    // if only left run
                while(ll++ < n){            //   copy it and break
                    q.push(q.front());
                    q.pop();
                }
                break;
            }
            ee = rr+r;                      // ee = pseudo end of right run
            if(ee > n)
                ee = n;
            // merge a pair of runs
            // stack == left / even run
            // queue == right / odd run
            size_t m = rr - ll;             // m = # elements in left run
            while(m--){                     //  pop/push left run to stack
                s.push(q.front());
                q.pop();
            }
            m = ee - rr;                    // m = # elements in right run
            while(1){
                if(q.front() > s.top()){    // (reverse for descending)
                    q.push(q.front());
                    q.pop();
                    if(--m == 0){           // if end right run
                        while(!s.empty()){  //   copy rest of left run
                            q.push(s.top());
                            s.pop();
                        }
                        break;              //   and break
                    }
                } else {
                    q.push(s.top());
                    s.pop();
                    if(s.empty()){          // if end left run
                        while(m--){         //   copy rest of right run
                            q.push(q.front());
                            q.pop();
                        }
                        break;              // and break
                    }
                }
            }                               // end merge pair
        }                                   // end merge pass
        r *= 2;                             // double run size
        if(r >= n)                          //  break if sort done
            break;
        // reverse left/even runs in q
        ee = 0;                             // pseudo end index
        while(ee < n){
            size_t ll = ee;                 // ll = pseudo start of left  run
            size_t rr = ll+r;               // rr = pseudo start of right run
            if(rr >= n){                    // if only left run
                while(ll++ < n){            //   copy it and break
                    q.push(q.front());
                    q.pop();
                }
                break;
            }
            ee = rr+r;                      // ee = pseudo end of right run
            if(ee > n)
                ee = n;
            size_t m = rr - ll;             // m = # elements in left run
            while(m--){                     // pop/push left run to s
                s.push(q.front());
                q.pop();
            }
            while(!s.empty()){              // pop/push s to q
                q.push(s.top());            //  (reverse left/even run)
                s.pop();
            }
            m = ee - rr;                    // m = # elements in right run
            while(m--){                     // copy odd run to q
                q.push(q.front());
                q.pop();
            }
        }                                   // end reverse left/even runs
    }                                       // end merge sort
    while(!q.empty()){                      // pop/push q to s
        s.push(q.front());
        q.pop();
    }
}