Sorting a queue in O(n log n) using at most 2 queue

Question

We were tasked to sort a queue in O(n log n) using basic functions such as enqueue, dequeue, peek, empty only. Additionally, we may use another queue to help us. No other data structures are allowed.

Having trouble coming up with a solution as I feel like this is possibly an modification of a divide-and-conquer problem but I am unable to come up with a solution using the 4 basic functions.

Is it possible to receive some hints to solve this problem?

Answer 1

Given queue A full and queue B empty, if A consists of sorted groups of w elements, then you can merge them in pairs to produce sorted groups of 2w elements as follows:

1. While(A.length - B.length > w), pull w elements out of A and put them in B. A and B will then both consist of sorted groups of w elements, plus some left over.

2. repeatedly pull w elements from both A and B, merging them onto the back of A to create sorted groups of 2w elements. Stop when all the elements have been processed (be careful not to pull elements from A that you already processed. You'll need to remember its original size). A will then consist of of sorted 2w groups, and B will be empty again.

Repeat the above procedure with w=1 (groups of 1 are always sorted), then w=2, w=4 ... w=2ⁿ, etc. until the whole queue is sorted.