


'''simple docstring'''


from __future__ import annotations






def 			__lowerCAmelCase			(__lowerCAmelCase   ,			__lowerCAmelCase ):
		_UpperCAmelCase		:							Tuple             =   0
		_UpperCAmelCase		:							Optional[Any]             =   len(__lowerCAmelCase ) - 1
		while left <= right:
				_UpperCAmelCase		:							List[str]             =   (left + right) // 2
				if left == right:
						if sorted_list[middle] < item:
								_UpperCAmelCase		:							Optional[int]             =   middle + 1
						break
				elif sorted_list[middle] < item:
						_UpperCAmelCase		:							int             =   middle + 1
				else:
						_UpperCAmelCase		:							Any             =   middle - 1
		sorted_list.insert(__lowerCAmelCase   ,			__lowerCAmelCase )
		return sorted_list






def 			__lowerCAmelCase			(__lowerCAmelCase   ,			__lowerCAmelCase ):
		_UpperCAmelCase		:							List[str]             =   []
		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 			__lowerCAmelCase			(__lowerCAmelCase ):
		_UpperCAmelCase		:							Any             =   len(__lowerCAmelCase )
		if length <= 1:
				return list_ad
		_UpperCAmelCase		:							Dict             =   length // 2
		return merge(sortlist_ad(list_ad[:middle] )   ,			sortlist_ad(list_ad[middle:] ) )






def 			__lowerCAmelCase			(__lowerCAmelCase ):

		if len(__lowerCAmelCase ) <= 1:
				return collection
		_UpperCAmelCase		:							Optional[int]             =   []
		_UpperCAmelCase		:							int             =   False
		for i in range(0   ,			len(__lowerCAmelCase )   ,			2 ):
				if i == len(__lowerCAmelCase ) - 1:
						_UpperCAmelCase		:							List[str]             =   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]] )
		_UpperCAmelCase		:							Dict             =   sortlist_ad(__lowerCAmelCase )
		_UpperCAmelCase		:							int             =   [i[0] for i in sorted_list_ad]
		result.append(sorted_list_ad[-1][1] )
		if has_last_odd_item:
				_UpperCAmelCase		:							Union[str, Any]             =   collection[-1]
				_UpperCAmelCase		:							str             =   binary_search_insertion(__lowerCAmelCase   ,			__lowerCAmelCase )
		_UpperCAmelCase		:							Any             =   False
		for i in range(len(__lowerCAmelCase ) - 1 ):
				if result[i] == collection[-1] and has_last_odd_item:
						_UpperCAmelCase		:							str             =   True
				_UpperCAmelCase		:							Optional[int]             =   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:
						_UpperCAmelCase		:							Tuple             =   result[: i + 2] + binary_search_insertion(result[i + 2 :]   ,			__lowerCAmelCase )
				else:
						_UpperCAmelCase		:							Tuple             =   result[: i + 1] + binary_search_insertion(result[i + 1 :]   ,			__lowerCAmelCase )

		return result


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







'''simple docstring'''


def 			__lowerCAmelCase			(__lowerCAmelCase ):
		return "".join(chr(ord(__lowerCAmelCase ) + 32 ) if "A" <= char <= "Z" else char for char in word )


if __name__ == "__main__":
						from doctest import testmod

						testmod()



