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

SortTwoQueues.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 SortTwoQueues {
    // 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()) {
            // Finds the smallest item in the 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);
                }
            }
            
            temp.add(smallest);
        }
        
        // Queue is now empty, with the numbers located at the back of temp.
        
        // Moves the temp numbers to the back, bringing the sorted numbers forward.
        for (int i = 0; i < tempOriginalSize; i++) {
            temp.add(temp.remove());
        }
        
        // Recover the sorted numbers and put them back in `queue`.
        // Temp is now back in its original state.
        for (int i = 0; i < queueOriginalSize; i++) {
            queue.add(temp.remove());
        }
    }
}