
"""simple docstring"""
from __future__ import annotations

def 				lowercase      (_lowerCAmelCase				,  _lowerCAmelCase		):
						__lowerCAmelCase        =       0
						__lowerCAmelCase        =       len(_UpperCAmelCase		) - 1
						while left <= right:
												__lowerCAmelCase        =       (left + right) // 2
												if left == right:
																		if sorted_list[middle] < item:
																								__lowerCAmelCase        =       middle + 1
																		break
												elif sorted_list[middle] < item:
																		__lowerCAmelCase        =       middle + 1
												else:
																		__lowerCAmelCase        =       middle - 1
						sorted_list.insert(_UpperCAmelCase				,  _UpperCAmelCase		)
						return sorted_list

def 				lowercase      (_lowerCAmelCase				,  _lowerCAmelCase		):
						__lowerCAmelCase        =       []
						while left and right:
												if left[0][0] < right[0][0]:
																		result.append(left.pop(0		)		)
												else:
																		result.append(right.pop(0		)		)
						return result + left + right

def 				lowercase      (_lowerCAmelCase		):
						__lowerCAmelCase        =       len(_UpperCAmelCase		)
						if length <= 1:
												return list_ad
						__lowerCAmelCase        =       length // 2
						return merge(sortlist_ad(list_ad[:middle]		)				,  sortlist_ad(list_ad[middle:]		)		)

def 				lowercase      (_lowerCAmelCase		):





						if len(_UpperCAmelCase		) <= 1:
												return collection
						__lowerCAmelCase        =       []
						__lowerCAmelCase        =       False
						for i in range(0				,  len(_UpperCAmelCase		)				,  2		):
												if i == len(_UpperCAmelCase		) - 1:
																		__lowerCAmelCase        =       True
												else:
																		if collection[i] < collection[i + 1]:
																								two_paired_list.append([collection[i], collection[i + 1]]		)
																		else:
																								two_paired_list.append([collection[i + 1], collection[i]]		)
						__lowerCAmelCase        =       sortlist_ad(_UpperCAmelCase		)
						__lowerCAmelCase        =       [i[0] for i in sorted_list_ad]
						result.append(sorted_list_ad[-1][1]		)
						if has_last_odd_item:
												__lowerCAmelCase        =       collection[-1]
												__lowerCAmelCase        =       binary_search_insertion(_UpperCAmelCase				,  _UpperCAmelCase		)
						__lowerCAmelCase        =       False
						for i in range(len(_UpperCAmelCase		) - 1		):
												if result[i] == collection[-1] and has_last_odd_item:
																		__lowerCAmelCase        =       True
												__lowerCAmelCase        =       sorted_list_ad[i][1]
												# If last_odd_item is inserted before the item's index,
												# you should forward index one more.
												if is_last_odd_item_inserted_before_this_index:
																		__lowerCAmelCase        =       result[: i + 2] + binary_search_insertion(result[i + 2 :]				,  _UpperCAmelCase		)
												else:
																		__lowerCAmelCase        =       result[: i + 1] + binary_search_insertion(result[i + 1 :]				,  _UpperCAmelCase		)

						return result


if __name__ == "__main__":
			SCREAMING_SNAKE_CASE_			      =					input('''Enter numbers separated by a comma:\n''').strip()
			SCREAMING_SNAKE_CASE_			      =					[int(item) for item in user_input.split(''',''')]
			print(merge_insertion_sort(unsorted))



"""simple docstring"""
from __future__ import annotations

from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE_			      =					TypeVar('''T''')
class      lowerCAmelCase_						(							A__				):



							'''simple docstring'''





							pass
class      lowerCAmelCase_						(							A__				):



							'''simple docstring'''





							pass
class      lowerCAmelCase_						(							Generic[T]				):



							'''simple docstring'''





							def __init__(				self  ,							snake_case_ = 10							)   ->       Tuple:
													__lowerCAmelCase        =       []
													__lowerCAmelCase        =       limit




							def __bool__(				self							)   ->       bool:
													return bool(self.stack							)




							def __str__(				self							)   ->       str:
													return str(self.stack							)




							def  A__		(				self  ,							snake_case_							)   ->       None:
													if len(self.stack							) >= self.limit:
																			raise StackOverflowError
													self.stack.append(snake_case_							)




							def  A__		(				self							)   ->       T:
													if not self.stack:
																			raise StackUnderflowError
													return self.stack.pop()




							def  A__		(				self							)   ->       T:
													if not self.stack:
																			raise StackUnderflowError
													return self.stack[-1]




							def  A__		(				self							)   ->       bool:
													return not bool(self.stack							)




							def  A__		(				self							)   ->       bool:
													return self.size() == self.limit




							def  A__		(				self							)   ->       int:
													return len(self.stack							)




							def __contains__(				self  ,							snake_case_							)   ->       bool:
													return item in self.stack

def 				lowercase      ():
						__lowerCAmelCase        =       Stack(10		)
						assert bool(_lowerCAmelCase		) is False
						assert stack.is_empty() is True
						assert stack.is_full() is False
						assert str(_lowerCAmelCase		) == "[]"

						try:
												__lowerCAmelCase        =       stack.pop()
												raise AssertionError  # This should not happen
						except StackUnderflowError:
												assert True  # This should happen

						try:
												__lowerCAmelCase        =       stack.peek()
												raise AssertionError  # This should not happen
						except StackUnderflowError:
												assert True  # This should happen

						for i in range(10		):
												assert stack.size() == i
												stack.push(_lowerCAmelCase		)

						assert bool(_lowerCAmelCase		)
						assert not stack.is_empty()
						assert stack.is_full()
						assert str(_lowerCAmelCase		) == str(list(range(10		)		)		)
						assert stack.pop() == 9
						assert stack.peek() == 8

						stack.push(100		)
						assert str(_lowerCAmelCase		) == str([0, 1, 2, 3, 4, 5, 6, 7, 8, 100]		)

						try:
												stack.push(200		)
												raise AssertionError  # This should not happen
						except StackOverflowError:
												assert True  # This should happen

						assert not stack.is_empty()
						assert stack.size() == 10

						assert 5 in stack
						assert 55 not in stack


if __name__ == "__main__":
			test_stack()
