
def     UpperCAmelCase__							(       __magic_name__						:     Tuple							,  __magic_name__						:     int							,  __magic_name__						:     Dict							,  __magic_name__						:     str  ):


					'''simple docstring'''

					if start == end:
										return start if lst[start] > item else start + 1
					if start > end:
										return start

					lowerCAmelCase		:					Optional[Any]  	=     (start + end) // 2
					if lst[mid] < item:
										return binary_search(__magic_name__							,  __magic_name__							,  mid + 1							,  __magic_name__  )
					elif lst[mid] > item:
										return binary_search(__magic_name__							,  __magic_name__							,  __magic_name__							,  mid - 1  )
					else:
										return mid
def     UpperCAmelCase__							(       __magic_name__						:     List[Any]  ):


					'''simple docstring'''

					lowerCAmelCase		:					Union[str, Any]  	=     len(__magic_name__  )

					for index in range(1							,  __magic_name__  ):
										lowerCAmelCase		:					Optional[int]  	=     lst[index]
										lowerCAmelCase		:					Dict  	=     binary_search(__magic_name__							,  __magic_name__							,  0							,  index - 1  )
										lowerCAmelCase		:					Union[str, Any]  	=     lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]

					return lst
def     UpperCAmelCase__							(       __magic_name__						:     Optional[int]							,  __magic_name__						:     List[str]  ):


					'''simple docstring'''

					if not left:
										return right

					if not right:
										return left

					if left[0] < right[0]:
										return [left[0], *merge(left[1:]							,  __magic_name__  )]

					return [right[0], *merge(__magic_name__							,  right[1:]  )]
def     UpperCAmelCase__							(       __magic_name__						:     str  ):


					'''simple docstring'''

					lowerCAmelCase		:					str  	=     len(__magic_name__  )
					lowerCAmelCase	,							lowerCAmelCase		:					Union[str, Any]  	=     [], []
					lowerCAmelCase		:					Union[str, Any]  	=     [lst[0]]
					lowerCAmelCase		:					Optional[Any]  	=     []
					lowerCAmelCase		:					List[Any]  	=     1
					while i < length:
										if lst[i] < lst[i - 1]:
															runs.append(__magic_name__  )
															lowerCAmelCase		:					Any  	=     [lst[i]]
										else:
															new_run.append(lst[i]  )
										i += 1
					runs.append(__magic_name__  )

					for run in runs:
										sorted_runs.append(insertion_sort(__magic_name__  )  )
					for run in sorted_runs:
										lowerCAmelCase		:					int  	=     merge(__magic_name__							,  __magic_name__  )

					return sorted_array
def     UpperCAmelCase__							(       ):


					'''simple docstring'''

					lowerCAmelCase		:					Tuple  	=     [5, 9, 10, 3, -4, 5, 1_78, 92, 46, -18, 0, 7]
					lowerCAmelCase		:					Optional[Any]  	=     tim_sort(__magic_name__  )
					print(__magic_name__  )


if __name__ == "__main__":
		main()


def     UpperCAmelCase__							(       __magic_name__						:     Tuple							,  __magic_name__						:     int							,  __magic_name__						:     Dict							,  __magic_name__						:     str  ):


					'''simple docstring'''

					if start == end:
										return start if lst[start] > item else start + 1
					if start > end:
										return start

					lowerCAmelCase		:					Optional[Any]  	=     (start + end) // 2
					if lst[mid] < item:
										return binary_search(__magic_name__							,  __magic_name__							,  mid + 1							,  __magic_name__  )
					elif lst[mid] > item:
										return binary_search(__magic_name__							,  __magic_name__							,  __magic_name__							,  mid - 1  )
					else:
										return mid
def     UpperCAmelCase__							(       __magic_name__						:     List[Any]  ):


					'''simple docstring'''

					lowerCAmelCase		:					Union[str, Any]  	=     len(__magic_name__  )

					for index in range(1							,  __magic_name__  ):
										lowerCAmelCase		:					Optional[int]  	=     lst[index]
										lowerCAmelCase		:					Dict  	=     binary_search(__magic_name__							,  __magic_name__							,  0							,  index - 1  )
										lowerCAmelCase		:					Union[str, Any]  	=     lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]

					return lst
def     UpperCAmelCase__							(       __magic_name__						:     Optional[int]							,  __magic_name__						:     List[str]  ):


					'''simple docstring'''

					if not left:
										return right

					if not right:
										return left

					if left[0] < right[0]:
										return [left[0], *merge(left[1:]							,  __magic_name__  )]

					return [right[0], *merge(__magic_name__							,  right[1:]  )]
def     UpperCAmelCase__							(       __magic_name__						:     str  ):


					'''simple docstring'''

					lowerCAmelCase		:					str  	=     len(__magic_name__  )
					lowerCAmelCase	,							lowerCAmelCase		:					Union[str, Any]  	=     [], []
					lowerCAmelCase		:					Union[str, Any]  	=     [lst[0]]
					lowerCAmelCase		:					Optional[Any]  	=     []
					lowerCAmelCase		:					List[Any]  	=     1
					while i < length:
										if lst[i] < lst[i - 1]:
															runs.append(__magic_name__  )
															lowerCAmelCase		:					Any  	=     [lst[i]]
										else:
															new_run.append(lst[i]  )
										i += 1
					runs.append(__magic_name__  )

					for run in runs:
										sorted_runs.append(insertion_sort(__magic_name__  )  )
					for run in sorted_runs:
										lowerCAmelCase		:					int  	=     merge(__magic_name__							,  __magic_name__  )

					return sorted_array
def     UpperCAmelCase__							(       ):


					'''simple docstring'''

					lowerCAmelCase		:					Tuple  	=     [5, 9, 10, 3, -4, 5, 1_78, 92, 46, -18, 0, 7]
					lowerCAmelCase		:					Optional[Any]  	=     tim_sort(__magic_name__  )
					print(__magic_name__  )


if __name__ == "__main__":
		main()
