4. (15 points) StackSort is a sorting algorithm that takes as input a list of distinct integers. It works in the following way: Set up consists of a right side, a left side with an empty stack in the middle. Start off with the list you want to sort on the right side. 51324 One by one, starting from the left-most element in the list, if the element is smaller than the head of the stack or the stack is empty, then push that element into the stack. Otherwise (if the element is larger than the head of the stack, then pop the head of the stack and put it on the left side.) When the right side is empty then pop the stack and append each element to the left side until the stack is empty. Tome (a) Draw out all steps of the StackSort algorithm on (4,1,3,2): (you may clearly handdraw the steps if you wish.) (b) If the original list has n elements, how many stack operations (push and pop) does StackSort take? Please give a brief justification for our answer. (c) Is StackSort reliable? Will it sort all strings? Either give a brief justification that it will always work or provide a counterexample. 4. (15 points) StackSort is a sorting algorithm that takes as input a list of distinct integers. It works in the following way: Set up consists of a right side, a left side with an empty stack in the middle. Start off with the list you want to sort on the right side. 51324 One by one, starting from the left-most element in the list, if the element is smaller than the head of the stack or the stack is empty, then push that element into the stack. Otherwise (if the element is larger than the head of the stack, then pop the head of the stack and put it on the left side.) When the right side is empty then pop the stack and append each element to the left side until the stack is empty. Tome (a) Draw out all steps of the StackSort algorithm on (4,1,3,2): (you may clearly handdraw the steps if you wish.) (b) If the original list has n elements, how many stack operations (push and pop) does StackSort take? Please give a brief justification for our answer. (c) Is StackSort reliable? Will it sort all strings? Either give a brief justification that it will always work or provide a counterexample