A short program that takes two queues and sorts them without using any auxiliary data structures.

SortTwoQueuesV2.java

// Michael Lee
// January 27, 2015
// Section BP
//
// This file takes two queues with numbers in random order and sorts them. 

import java.util.*;

public class SortTwoQueuesV2 {
    // The main starting point of the program.
    public static void main(String[] args) {
        Queue<Integer> q1 = new LinkedList<Integer>(Arrays.asList(1, 3, 2, 5, 4, 0));
        Queue<Integer> q2 = new LinkedList<Integer>(Arrays.asList(1, 2, 5, 1, 3));
        
        display("BEFORE", q1, q2);
        sortQueues(q1, q2);
        display("AFTER", q1, q2);
    }
    
    // A utility function that displays a heading then two queues.
    public static void display(String heading, Queue<Integer> a, Queue<Integer> b) {
        System.out.println(heading);
        System.out.println(a);
        System.out.println(b);
        System.out.println();
    }

    // Takes two queues, and puts them both into sorted order. Neither queues 
    // should be null. The queues are permitted to either have numbers in them,
    // or be empty.
    public static void sortQueues(Queue<Integer> a, Queue<Integer> b) {
        sortOne(a, b);
        sortOne(b, a);
    }

    // Sorts a single queue, using the other as a temporary. The temp queue
    // will be left unchanged. Neither queue may be empty.
    public static void sortOne(Queue<Integer> queue, Queue<Integer> temp) {
        int queueOriginalSize = queue.size();
        int tempOriginalSize = temp.size();
        
        // Moves numbers to the back of the temp queue in sorted order.
        while (!queue.isEmpty()) {
            temp.add(removeSmallest(queue));
        }
        
        // We now restore both queues (cycle sorted numbers to the front, 
        // then move them back to the queue).
        cycle(temp, tempOriginalSize);
        move(temp, queue, queueOriginalSize);
    }
    
    // Removes the smallest number from the queue. May scramble the order
    // of the queue. Assumes that the queue has at least one element inside.
    private static int removeSmallest(Queue<Integer> queue) {
        int smallest = queue.remove();
        for (int i = 0; i < queue.size(); i++) {
            int next = queue.remove();
            
            // Cumulative sum -- keep looking for the smallest number
            if (next < smallest) {
                queue.add(smallest);
                smallest = next;
            } else {
                queue.add(next);
            }
        }
        return smallest;
    }
    
    // Cycles through the queue exactly `n` times. 
    private static void cycle(Queue<Integer> queue, int n) {
        for (int i = 0; i < n; i++) {
            queue.add(queue.remove());
        }
    }
    
    // Moves the first `n` elements in `source` to the `target`.
    private static void move(Queue<Integer> source, Queue<Integer> target, int n) {
        for (int i = 0; i < n; i++) {
            target.add(source.remove());
        }
    }
}