

from __future__ import annotations






def        lowerCamelCase_  (				UpperCAmelCase_				:  List[Any]				,							UpperCAmelCase_				:  Union[str, Any]						)    ->					Optional[Any]:




	'''simple docstring'''




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






def        lowerCamelCase_  (				UpperCAmelCase_				:  List[Any]				,							UpperCAmelCase_				:  Optional[Any]						)    ->					Optional[int]:




	'''simple docstring'''




	_UpperCamelCase :		Dict								=    []
	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_  (				UpperCAmelCase_				:  Tuple						)    ->					Dict:




	'''simple docstring'''




	_UpperCamelCase :		Any								=    len(UpperCAmelCase_						)
	if length <= 1:
		return list_ad
	_UpperCamelCase :		Dict								=    length // 2
	return merge(sortlist_ad(list_ad[:middle]						)				,							sortlist_ad(list_ad[middle:]						)						)






def        lowerCamelCase_  (				UpperCAmelCase_				:  list[int]						)    ->					list[int]:




	'''simple docstring'''




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

	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))







import posixpath
from pathlib import Path
from unittest.mock import patch

import pytest
from fsspec.implementations.local import AbstractFileSystem, LocalFileSystem, stringify_path
from fsspec.registry import _registry as _fsspec_registry







class 						lowercase     (					_lowercase				):


		"""simple docstring"""




		a__       							=	"mock"


		def __init__(					self						,							*__snake_case						,							__snake_case						,							**__snake_case):
			super().__init__()
			_UpperCamelCase :		str								=    LocalFileSystem(*__snake_case						,							**__snake_case)
			_UpperCamelCase :		str								=    Path(__snake_case).resolve().as_posix() + '/'


		def 		A__       (					self						,							__snake_case						,							*__snake_case						,							**__snake_case):
			_UpperCamelCase :		int								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			return self._fs.mkdir(__snake_case						,							*__snake_case						,							**__snake_case)


		def 		A__       (					self						,							__snake_case						,							*__snake_case						,							**__snake_case):
			_UpperCamelCase :		List[str]								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			return self._fs.makedirs(__snake_case						,							*__snake_case						,							**__snake_case)


		def 		A__       (					self						,							__snake_case):
			_UpperCamelCase :		Dict								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			return self._fs.rmdir(__snake_case)


		def 		A__       (					self						,							__snake_case						,							__snake_case=True						,							*__snake_case						,							**__snake_case):
			_UpperCamelCase :		Union[str, Any]								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			_UpperCamelCase :		Tuple								=    self._fs.ls(__snake_case						,							detail=__snake_case						,							*__snake_case						,							**__snake_case)
			if detail:
				return [{**info, "name": info["name"][len(self.local_root_dir) :]} for info in out]
			else:
				return [name[len(self.local_root_dir) :] for name in out]


		def 		A__       (					self						,							__snake_case						,							*__snake_case						,							**__snake_case):
			_UpperCamelCase :		Optional[Any]								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			_UpperCamelCase :		Optional[Any]								=    dict(self._fs.info(__snake_case						,							*__snake_case						,							**__snake_case))
			_UpperCamelCase :		Dict								=    out['name'][len(self.local_root_dir) :]
			return out


		def 		A__       (					self						,							__snake_case						,							__snake_case						,							*__snake_case						,							**__snake_case):
			_UpperCamelCase :		str								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			_UpperCamelCase :		Tuple								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			return self._fs.cp_file(__snake_case						,							__snake_case						,							*__snake_case						,							**__snake_case)


		def 		A__       (					self						,							__snake_case						,							*__snake_case						,							**__snake_case):
			_UpperCamelCase :		Dict								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			return self._fs.rm_file(__snake_case						,							*__snake_case						,							**__snake_case)


		def 		A__       (					self						,							__snake_case						,							*__snake_case						,							**__snake_case):
			_UpperCamelCase :		int								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			return self._fs.rm(__snake_case						,							*__snake_case						,							**__snake_case)


		def 		A__       (					self						,							__snake_case						,							*__snake_case						,							**__snake_case):
			_UpperCamelCase :		Dict								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			return self._fs._open(__snake_case						,							*__snake_case						,							**__snake_case)


		def 		A__       (					self						,							__snake_case):
			_UpperCamelCase :		Dict								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			return self._fs.created(__snake_case)


		def 		A__       (					self						,							__snake_case):
			_UpperCamelCase :		Dict								=    posixpath.join(self.local_root_dir						,							self._strip_protocol(__snake_case))
			return self._fs.modified(__snake_case)






		@classmethod
		def 		A__       (					cls						,							__snake_case):
			_UpperCamelCase :		List[Any]								=    stringify_path(__snake_case)
			if path.startswith('mock://'):
				_UpperCamelCase :		int								=    path[7:]
			return path







class 						lowercase     (					_lowercase				):


		"""simple docstring"""




		a__       							=	"tmp"
		a__       							=	None


		def __init__(					self						,							*__snake_case						,							**__snake_case):
			assert self.tmp_dir is not None, "TmpDirFileSystem.tmp_dir is not set"
			super().__init__(*__snake_case						,							**__snake_case						,							local_root_dir=self.tmp_dir						,							auto_mkdir=__snake_case)






		@classmethod
		def 		A__       (					cls						,							__snake_case):
			_UpperCamelCase :		Optional[int]								=    stringify_path(__snake_case)
			if path.startswith('tmp://'):
				_UpperCamelCase :		Optional[Any]								=    path[6:]
			return path






@pytest.fixture
def        lowerCamelCase_  (				)    ->					Dict:




	'''simple docstring'''




	_UpperCamelCase :		List[str]								=    MockFileSystem
	_UpperCamelCase :		Optional[int]								=    TmpDirFileSystem
	yield
	del _fsspec_registry["mock"]
	del _fsspec_registry["tmp"]






@pytest.fixture
def        lowerCamelCase_  (				UpperCAmelCase_				:  Any				,							UpperCAmelCase_				:  Optional[int]						)    ->					Optional[int]:




	'''simple docstring'''




	_UpperCamelCase :		str								=    tmp_path_factory.mktemp('mockfs'						)
	return MockFileSystem(local_root_dir=UpperCAmelCase_				,							auto_mkdir=UpperCAmelCase_						)







@pytest.fixture
def        lowerCamelCase_  (				UpperCAmelCase_				:  Tuple				,							UpperCAmelCase_				:  Union[str, Any]						)    ->					int:




	'''simple docstring'''




	_UpperCamelCase :		Dict								=    tmp_path_factory.mktemp('tmpfs'						)
	with patch.object(UpperCAmelCase_				,							'tmp_dir'				,							UpperCAmelCase_						):
		yield TmpDirFileSystem()




