Sorting a Stack Recursively (25 points)

In this lab assignment, you will create a Java application that sorts a stack recursively.

Consider the following algorithm to sort the entries in a stack S_1:

1. First create two empty stacks, S₂ and S₃. At any given time, stack S₂ will hold the entries in sorted order, with the smallest at the top of the stack. (You are sorting in ascending order.)

2. Put the top entry of S₁ into T (a variable that can hold stack elements)

3. Pop and consider the top entry T of S₁.

4. Pop entries of stack S₂ and push them onto stack S₃ until you reach the correct place to put T.

5. Then push T onto S₂.

6. Next move entries from S₃ to S₂.

7. Repeat until S₁ is empty and S₂ contains the sorted stack.

Requirements:

1. Your application uses unbounded stacks from chapter 2 in your text.

2. Write a main method to create an unsorted stack and display the unsorted stack.

3. Send the stack to a method for sorting. Upon return from the method, display the now sorted stack.

4. Write a recursive method that accepts an unsorted Stack and returns a sorted Stack. The method should be generic and work for all types of stacks.

5. Test your recursive method to make sure it works for different types of stacks.

Hint: May want to use a public method that accepts the original stack and then creates the two additional stacks needed. This method then calls a private method that accepts all three stacks and does the recursive sort. Your methods should make sure all types of stacks passed contain comparable objects. Refer to the generic presentation in Shared Files.

Clearly label all the output written to the console.