Please help me with the following questions: (Please write out all the solutions step-by-step and justify your answers)

3. (16 points) StackSort is a sorting algorithm that takes as input a permutation. 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 permutation you want to sort on the right side. 51324 One by one, starting from the left-most element in the permutation, 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. 51324 1324 324 1 324 1 24 NM 5 5 5 unw 12 4 1234 123 1234 12345 un w 5 (a) If the permutation is of length n, how many stack operations (push and pop) does StackSort take? What is the runtime of this algorithm in notation? Please give a brief justification for your answer. (b) StackSort is not a reliable sorting algorithm. Give an example of a permutation that is not able to be sorted using StackSort and explain what goes wrong. (c) A permutation is called stack-sortable if you can sort it using StackSort. Let SS(n) be the number of stack-sortable permutations of length n. Give an argument why SS(n)