[SOLVED] CS

QUESTION 4: Stacks

4 marks, ~10 minutes

Heres a mystery_sort function that is meant to sort some kind of list, i.e.,
lists that satisfy certain preconditions.

Read the code and answer the questions below.

def mystery_sort(lst: List[int]) -> List[int]:

s1 = Stack()
s2 = Stack()
flag = True
i = 0
while i < len(lst):if flag and (s1.is_empty() or lst[i] > s1.peek()):
s1.push(lst[i])
else:
flag = False
s2.push(lst[i])
i += 1
res = []
while not s2.is_empty():
res.append(s2.pop())
while not s1.is_empty():
s2.push(s1.pop())
while not s2.is_empty():
res.append(s2.pop())
return res

(a) Below, provide an example input such that mystery_sort return a sorted
copy of the list in non-decreasing order.

Requirements:
the input list must be of size 7
the input must NOT be sorted in either non-increasing or non-decreasing order.

TODO:
Write your input here:

(b) Below, provide an example inputthat is sorted in non-decreasing order
but the return value of mystery_sort is NOT sorted.

Requirement:
the input list must be of size 5

TODO:
Write your input here:

(c) Describe a precondition for the input list such that the mystery_sort()
method returns a sorted copy of the input in non-decreasing order.
Your precondition should include as many valid inputs as possible.

TODO:
Write your precondition here:

(d) What is the time complexity of mystery_sort in terms of n, the size of the
input list? Assume that the Stack is implemented in the efficient way that we
learned in this course.

TODO:
Write your answer in big-Oh (O(???)) and briefly justify.