Given a stack, the task is to sort it such that the top of the stack has the greatest element.
Example 1:
Input:
Stack: 3 2 1
Output: 3 2 1
Example 2:
Input:
Stack: 11 2 32 3 41
Output: 41 32 11 3 2
Your Task: 
You don't have to read input or print anything. Your task is to complete the function sort() which sorts the elements present in the given stack. (The sorted stack is printed by the driver's code by popping the elements of the stack.)
Expected Time Complexity: O(N*N)
Expected Auxilliary Space: O(N) recursive.
Constraints:
1<=N<=100

Difficulty: EASY
Tags: Data structures

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(N) recursive.

Starter code:
class Solution:

    # your task is to complete this function

    # function sort the stack such that top element is max

    # funciton should return nothing

    # s is a stack

    def sorted(self, s):

        # Code here



Solutions:
class Solution:

	def sorted(self, s):
		s.sort()


class Solution:

	def sorted(self, s):
		arr = [s.pop() for i in range(len(s))]
		arr.sort()
		for i in range(len(arr)):
			s.append(arr[i])


class Solution:

	def sorted(self, s):
		if len(s) == 0:
			return
		else:
			num = s.pop()
			self.sorted(s)
			self.sorted_num(s, num)

	def sorted_num(self, s, num):
		if len(s) == 0 or num >= s[-1]:
			s.append(num)
			return
		temp = s.pop()
		self.sorted_num(s, num)
		s.append(temp)


class Solution:

	def sorted(self, s):
		if not len(s):
			return
		num = s.pop()
		self.sorted(s)
		self.sortedInsert(s, num)

	def sortedInsert(self, s, element):
		if len(s) == 0 or element >= s[-1]:
			s.append(element)
			return
		temp = s.pop()
		self.sortedInsert(s, element)
		s.append(temp)


class Solution:

	def sorted(self, s):
		st = []
		while s:
			temp = s.pop()
			while st and st[-1] < temp:
				s.append(st.pop())
			st.append(temp)
		while st:
			s.append(st.pop())
		return s


class Solution:

	def sortedl(self, s, n):
		if n == 1:
			return
		count = 0
		for i in range(n - 1):
			if s[i] > s[i + 1]:
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				count += 1
		if count == 0:
			return
		self.sortedl(s, n)

	def sorted(self, s):
		l = len(s)
		self.sortedl(s, l)


class Solution:

	def sorted(self, stack):

		def sortInsert(stack, val):
			if len(stack) == 0 or stack[-1] < val:
				stack.append(val)
				return
			temp = stack.pop()
			sortInsert(stack, val)
			stack.append(temp)

		def sort(stack):
			if len(stack) == 0:
				return
			val = stack.pop()
			sort(stack)
			sortInsert(stack, val)
		sort(stack)


class Solution:

	def sortedinsert(self, s, top):
		if len(s) == 0:
			s.append(top)
			return
		if top <= s[0]:
			s.insert(0, top)
			return
		tmp = s.pop(0)
		self.sortedinsert(s, top)
		s.insert(0, tmp)

	def sorted(self, s):
		if len(s) == 0:
			return
		top = s.pop(0)
		self.sorted(s)
		self.sortedinsert(s, top)


class Solution:

	def sorted(self, s):
		s.sort()
		return s[::-1]


class Solution:

	def sorted(self, s):

		def mergeSort(left, right):
			if left >= right:
				return
			mid = left + (right - left) // 2
			mergeSort(left, mid)
			mergeSort(mid + 1, right)
			low = left
			high = mid + 1
			temp = []
			while low <= mid and high <= right:
				if arr[low] <= arr[high]:
					temp.append(arr[low])
					low += 1
				else:
					temp.append(arr[high])
					high += 1
			while low <= mid:
				temp.append(arr[low])
				low += 1
			while high <= right:
				temp.append(arr[high])
				high += 1
			for i in range(left, right + 1):
				s[i] = temp[i - left]
		mergeSort(0, len(s) - 1)


class Solution:

	def sorted(self, s):

		def insert_sorted(s, num):
			if len(s) == 0:
				s.append(num)
				return
			if s[-1] < num:
				s.append(num)
				return
			n = s.pop()
			insert_sorted(s, num)
			s.append(n)

		def solve(s):
			if len(s) == 0:
				return
			num = s.pop()
			solve(s)
			insert_sorted(s, num)
		solve(s)


class Solution:

	def sorted(self, s):
		if s:
			temp = s.pop()
			self.sorted(s)
			self.help(s, temp)
		return s

	def help(self, s, temp):
		if not s or s[-1] <= temp:
			s.append(temp)
			return
		else:
			element = s.pop()
			self.help(s, temp)
			s.append(element)


class Solution:

	def sorted(self, s):
		if len(s) == 1:
			return
		temp = s.pop()
		self.sorted(s)
		self.insert_at_place(s, temp)

	def insert_at_place(self, s, item):
		if not s or s[-1] <= item:
			s.append(item)
			return
		else:
			temp = s.pop()
			self.insert_at_place(s, item)
			s.append(temp)


class Solution:

	def sorted(self, s):
		for i in range(len(s)):
			for j in range(i, len(s)):
				if s[i] > s[j]:
					(s[i], s[j]) = (s[j], s[i])
		return s


class Solution:

	def sorted(self, s):

		def sortstack():
			if s:
				x = s.pop()
				sortstack()
				insertatcorrectposition(x)
			return s

		def insertatcorrectposition(x):
			if not s or s[-1] < x:
				s.append(x)
			else:
				ele = s.pop()
				insertatcorrectposition(x)
				s.append(ele)
			return s
		return sortstack()


class Solution:

	def sorted(self, s):
		a = s.sort()
		return a


class Solution(object):

	def insertAtRightPosition(self, stack, num):
		if not stack:
			stack.append(num)
		elif stack[-1] > num:
			top = stack.pop()
			self.insertAtRightPosition(stack, num)
			stack.append(top)
		else:
			stack.append(num)
		return stack

	def sorted(self, stack):
		if stack:
			top = stack.pop()
			self.sorted(stack)
			self.insertAtRightPosition(stack, top)
		return stack


class Solution:

	def sorted(self, s):
		if not s:
			return
		top = s.pop()
		self.sorted(s)
		self.insert(s, top)

	def insert(self, s, value):
		if not s or s[-1] <= value:
			s.append(value)
			return
		top = s.pop()
		self.insert(s, value)
		s.append(top)


class Solution:

	def sorted(self, s):
		self.sort(s)
		return s

	def sort(self, arr):
		if len(arr) == 1:
			return
		temp = arr[-1]
		arr.pop()
		self.sort(arr)
		self.insert(arr, temp)

	def insert(self, arr, temp):
		if len(arr) == 0 or arr[-1] <= temp:
			arr.append(temp)
			return
		val = arr[-1]
		arr.pop()
		self.insert(arr, temp)
		arr.append(val)


class Solution:

	def sorted(self, s):
		if not s:
			return
		num = s.pop()
		self.sorted(s)
		self.helper(s, num)

	def helper(self, st, n):
		if not st or st[-1] < n:
			st.append(n)
			return
		num = st.pop()
		self.helper(st, n)
		st.append(num)


class Solution:

	def sorted(self, stack):
		aux_stack = []
		while stack:
			temp = stack.pop()
			while aux_stack and aux_stack[-1] < temp:
				stack.append(aux_stack.pop())
			aux_stack.append(temp)
		while aux_stack:
			stack.append(aux_stack.pop())


class Solution:

	def insert(self, s, ele):
		if len(s) == 0:
			s.append(ele)
			return
		top = s.pop()
		if top > ele:
			self.insert(s, ele)
			s.append(top)
		else:
			s.append(top)
			s.append(ele)

	def sorted(self, s):
		if len(s) == 0:
			return
		top = s.pop()
		self.sorted(s)
		self.insert(s, top)


class Solution:

	def sorted(self, s):

		def f1(s, a):
			if len(s) == 0 or s[-1] <= a:
				s.append(a)
			else:
				x = s.pop()
				f1(s, a)
				s.append(x)

		def f2(s):
			if s:
				x = s.pop()
				f2(s)
				f1(s, x)
		return f2(s)


class Solution:

	def sortedInsert(self, s, num):
		if len(s) == 0 or (len(s) > 0 and s[-1] < num):
			s.append(num)
			return 0
		n = s.pop()
		self.sortedInsert(s, num)
		s.append(n)

	def sorted(self, s):
		if len(s) == 0:
			return 0
		n = s.pop()
		self.sorted(s)
		self.sortedInsert(s, n)


class Solution:

	def sorted(self, stack):
		buffer_stack = [0]
		while stack:
			top = stack.pop()
			while buffer_stack and buffer_stack[-1] < top:
				stack.append(buffer_stack.pop())
			buffer_stack.append(top)
		while buffer_stack:
			stack.append(buffer_stack.pop())
		stack.pop(0)
		return stack


class Solution:

	def sorted(self, s):
		if len(s) == 0:
			return s
		top = s.pop()
		self.sorted(s)
		self.insertSorted(top, s)
		return s

	def insertSorted(self, ele, st):
		if len(st) == 0:
			st.append(ele)
			return
		if len(st) and ele >= st[-1]:
			st.append(ele)
			return
		target = st.pop()
		self.insertSorted(ele, st)
		st.append(target)


class Solution:

	def sorted(self, s):

		def mini(stack, slow, fast, high):
			if fast == high:
				return
			if stack[slow] < stack[fast]:
				(stack[slow], stack[fast]) = (stack[fast], stack[slow])
			mini(stack, slow + 1, fast + 1, high)

		def sorting(stack, high):
			if high == 1:
				return
			mini(stack, 0, 1, high)
			sorting(stack, high - 1)
		sorting(s, len(s))
		s.reverse()


class Solution:

	def sorted(self, s):

		def insert(stack, temp):
			if len(stack) == 0 or temp > stack[-1]:
				stack.append(temp)
				return
			value = stack.pop()
			insert(stack, temp)
			stack.append(value)
			return

		def sorting(stack):
			if len(stack) == 1:
				return
			temp = stack.pop()
			sorting(stack)
			insert(stack, temp)
		sorting(s)


class Solution:

	def sorted(self, s):
		st = []
		while len(s) > 0:
			top = s.pop()
			while len(st) > 0 and st[-1] < top:
				s.append(st.pop())
			st.append(top)
			while len(s) > 0 and s[-1] < st[-1]:
				st.append(s.pop())
		while len(st) > 0:
			s.append(st.pop())


class Solution:

	def sortRec(self, s, top):
		if len(s) == 0 or s[-1] <= top:
			s.append(top)
			return
		else:
			n = s.pop()
			self.sortRec(s, top)
			s.append(n)

	def sorted(self, s):
		if len(s) == 0:
			return
		else:
			top = s.pop()
			self.sorted(s)
			self.sortRec(s, top)


class Solution:

	def merg(self, a, b, s):
		(i, j, k) = (0, 0, 0)
		while i < len(a) and j < len(b):
			if a[i] < b[j]:
				s[k] = a[i]
				i = i + 1
				k = k + 1
			else:
				s[k] = b[j]
				j = j + 1
				k = k + 1
		while i < len(a):
			s[k] = a[i]
			i = i + 1
			k = k + 1
		while j < len(b):
			s[k] = b[j]
			j = j + 1
			k = k + 1

	def sorted(self, s):
		if len(s) == 0 and len(s) == 1:
			return
		mid = len(s) // 2
		a = sorted(s[:mid])
		b = sorted(s[mid:])
		self.merg(a, b, s)


class Solution:

	def sorted(self, stack):
		stack2 = []
		while stack:
			stack3 = []
			top = stack.pop()
			while stack2 and top > stack2[-1]:
				stack3.append(stack2.pop())
			stack2.append(top)
			while stack3:
				top3 = stack3.pop()
				stack2.append(top3)
		while stack2:
			top2 = stack2.pop()
			stack.append(top2)


class Solution:

	def sorted(self, s):
		s.sort()
		i = 0
		j = len(s) - 1


class Solution:

	def sorted_insert(self, s, ele):
		if len(s) == 0 or s[-1] < ele:
			s.append(ele)
		else:
			tmp = s.pop()
			self.sorted_insert(s, ele)
			s.append(tmp)

	def sorted(self, s):
		if s:
			tmp = s.pop()
			self.sorted(s)
			self.sorted_insert(s, tmp)


class Solution:

	def sorted(self, s):
		for i in range(len(s)):
			for j in range(0, len(s) - i - 1):
				if s[j] > s[j + 1]:
					(s[j], s[j + 1]) = (s[j + 1], s[j])
		return arr


from collections import deque

class Solution:

	def sorted(self, s):
		d = deque()
		while s:
			tmp = s.pop()
			while d and tmp < d[-1]:
				p = d.pop()
				s.append(p)
			d.append(tmp)
		while d:
			print(d.pop(), end=' ')


class Solution:

	def sorted(self, s):
		s.sort()
		return reversed(s)


class Solution:

	def insert(self, stack, item):
		if len(stack) == 0 or item > stack[-1]:
			stack.append(item)
		else:
			temp = stack.pop()
			self.insert(stack, item)
			stack.append(temp)

	def sorted(self, stack):
		if len(stack) != 0:
			temp = stack.pop()
			self.sorted(stack)
			self.insert(stack, temp)


class Solution:

	def sorted(self, s):
		for i in range(len(s)):
			for j in range(i + 1, len(s)):
				if s[i] > s[j]:
					(s[i], s[j]) = (s[j], s[i])
				else:
					continue
		return s


class Solution:

	def insert_at_sorted_position(self, s, d):
		if len(s) == 0 or s[-1] <= d:
			s.append(d)
			return
		data = s.pop()
		self.insert_at_sorted_position(s, d)
		s.append(data)

	def sorted(self, s):
		if len(s) == 0:
			return
		d = s.pop()
		self.sorted(s)
		self.insert_at_sorted_position(s, d)
		return s


class Solution:

	def sortedInsert(self, s, item):
		if not s or item > s[-1]:
			s.append(item)
		else:
			temp = s.pop()
			self.sortedInsert(s, item)
			s.append(temp)

	def sorted(self, s):
		if s:
			temp = s.pop()
			self.sorted(s)
			self.sortedInsert(s, temp)


class Solution:

	def sorted(self, s):
		if len(s) == 0:
			return
		num = s[-1]
		s.pop()
		self.sorted(s)
		self.sort_stack(s, num)

	def sort_stack(self, s, num):
		if len(s) == 0 or s[-1] < num:
			s.append(num)
			return
		x = s.pop()
		self.sort_stack(s, num)
		s.append(x)
		return


class Solution:

	def sorted(self, s):
		arr = []
		for i in range(len(s)):
			arr.append(s.pop())
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				if arr[i] > arr[j]:
					temp = arr[i]
					arr[i] = arr[j]
					arr[j] = temp
		for i in range(len(arr)):
			s.append(arr[i])


class Solution:

	def sorted(self, s):
		if not s:
			return
		x = s.pop()
		self.sorted(s)
		tempStack = []
		while s and s[-1] > x:
			tempStack.append(s.pop())
		s.append(x)
		while tempStack:
			s.append(tempStack.pop())


from heapq import *

class Solution:

	def sorted(self, s):
		heap = []
		for i in s:
			heappush(heap, -i)
		for i in reversed(range(len(s))):
			s[i] = -heappop(heap)
		return s


class Solution:

	def sorted(self, s):

		def sort(stack, x):
			if not stack:
				stack.append(x)
				return stack
			if x < stack[-1]:
				a = stack.pop()
				stack = sort(stack, x)
				stack.append(a)
				return stack
			else:
				stack.append(x)
				return stack

		def helping(stack):
			if not stack:
				return stack
			else:
				a = stack.pop()
				stack = helping(stack)
				if not stack:
					stack.append(a)
					return stack
				else:
					return sort(stack, a)
		return helping(s)


class Solution:

	def sorted(self, s):
		s.sort()
		p = []
		for i in range(len(s) - 1, 0, -1):
			p.append(s[i])
		return p


class Solution:

	def sorted(self, s):
		if len(s) != 0:
			temp = s.pop()
			self.sorted(s)
			self.insertStack(s, temp)

	def insertStack(self, s, element):
		if len(s) == 0 or element > s[-1]:
			s.append(element)
		else:
			temp = s.pop()
			self.insertStack(s, element)
			s.append(temp)


class Solution:

	def sorted(self, s):
		s.sort(reverse=False)


class Solution:

	def sorted(self, s):

		def helper(stack):
			if len(stack) == 1:
				return
			top = stack.pop()
			helper(stack)
			temp = []
			while stack and stack[-1] > top:
				temp.append(stack.pop())
			stack.append(top)
			while temp:
				stack.append(temp.pop())
		helper(s)
		return s


class Solution:

	def sorted(self, s):
		if len(s) != 0:
			temp = s.pop()
			self.sorted(s)
			self.insert(s, temp)

	def insert(self, s, ele):
		if len(s) == 0 or ele > s[-1]:
			s.append(ele)
			return
		else:
			temp = s.pop()
			self.insert(s, ele)
			s.append(temp)


class Solution:

	def sorted(self, s):
		res = []
		st = [s[0]]
		for i in range(1, len(s)):
			if st and st[-1] >= s[i]:
				st.append(s[i])
			else:
				while st and st[-1] < arr[i]:
					res.append(st.pop())
				st.append(s[i])
				st.extend(res[::-1])
				res = []
		for i in range(len(s)):
			s[i] = st[len(st) - 1 - i]
		return s


class Solution:

	def sorted(self, s):
		n = len(s)
		for i in range(n):
			for j in range(n - i - 1):
				if s[j] > s[j + 1]:
					(s[j], s[j + 1]) = (s[j + 1], s[j])


class Solution:

	def insert(self, stack, ele):
		if len(stack) == 0:
			stack.append(ele)
			return
		if stack[-1] > ele:
			t_ele = stack.pop()
			self.insert(stack, ele)
			stack.append(t_ele)
		else:
			stack.append(ele)

	def sorted(self, stack):
		if len(stack) == 0:
			return
		ele = stack.pop()
		self.sorted(stack)
		self.insert(stack, ele)


def sort_stack_using_recursion(input_stack: []):
	if len(input_stack) == 0:
		return
	x = input_stack.pop(-1)
	sort_stack_using_recursion(input_stack)
	add_value_to_stack(input_stack, x)

def add_value_to_stack(input_stack, value: int):
	if len(input_stack) == 0:
		input_stack.append(value)
		return
	if input_stack[-1] <= value:
		input_stack.append(value)
		return
	x = input_stack.pop(-1)
	add_value_to_stack(input_stack, value)
	input_stack.append(x)

def sort_stack_main(input_stack: []):
	sort_stack_using_recursion(input_stack)
	return input_stack

class Solution:

	def sorted(self, s):
		return sort_stack_main(s)


class Solution:

	def sortb(self, s, n):
		if n is None:
			n = self.length
		count = 0
		if n == 1:
			return
		for i in range(n - 1):
			if s[i] > s[i + 1]:
				(s[i], s[i + 1]) = (s[i + 1], s[i])
				count = count + 1
		if count == 0:
			return
		self.sortb(s, n - 1)

	def sorted(self, s):
		n = len(s)
		self.sortb(s, n)


class Solution:

	def sorted(self, s):
		m = sorted(s)
		for i in range(len(s)):
			s[i] = m[i]