Question

Write an Insertion Sort algorithm for integer key values. However, here’s the catch: The input is a stack (not an array), and the only variables that your algorithm may use are a fixed number of integers and a fixed number of stacks. The algorithm should return a stack containing the records in sorted order (with the least value being at the top of the stack).

Answer 1

Answer:

Create a temporary stack say tmpStack.

While input stack is NOT empty do this:

Pop an element from input stack call it temp

while temporary stack is NOT empty and top of temporary stack is greater than temp,

pop from temporary stack and push it to the input stack

push temp in temporary stack

Explanation:

I hope it is very helpful for you