## Sort a stack without assumptions of implementation

Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Solution
The idea is simple enough: we use another stack as an auxiliary one. Then we pop items from the original stack and push into the auxiliary stack into the correct position. The time complexity is $O(N^{2})$. It’s similar as Insertion Sort.

```	public static Stack<Integer> sort(Stack<Integer> stack) {
Stack<Integer> auxiliary = new Stack<Integer>();
while (!stack.isEmpty()) {
Integer value = stack.pop();
while (!auxiliary.isEmpty() && value < auxiliary.peek())
stack.push(auxiliary.pop());
auxiliary.push(value);
}
return auxiliary;
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c910dce2a906', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c910dce2a931',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c910dce2a933',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

1. thanks