






"""simple docstring"""


from __future__ import annotations


def 					UpperCAmelCase			(				a__    ,			a__   ):





						'''simple docstring'''






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


def 					UpperCAmelCase			(				a__    ,			a__   ):





						'''simple docstring'''






						lowerCAmelCase      :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 					UpperCAmelCase			(				a__   ):





						'''simple docstring'''






						lowerCAmelCase      :Tuple				  = len(a__   )
						if length <= 1:
												return list_ad
						lowerCAmelCase      :Optional[int]				  = length // 2
						return merge(sortlist_ad(list_ad[:middle]   )    ,			sortlist_ad(list_ad[middle:]   )   )


def 					UpperCAmelCase			(				a__   ):





						'''simple docstring'''






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

						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 .number_theory.prime_numbers import next_prime




class 	__UpperCamelCase    :
					def __init__(       self       :  List[str]    ,   UpperCAmelCase       :  int    ,   UpperCAmelCase       :  int | None = None    ,   UpperCAmelCase       :  float | None = None    ,   )  ->					None:
											lowerCAmelCase      :Tuple				  = size_table
											lowerCAmelCase      :List[Any]				  = [None] * self.size_table
											lowerCAmelCase      :Tuple				  = 0.7_5 if lim_charge is None else lim_charge
											lowerCAmelCase      :str				  = 1 if charge_factor is None else charge_factor
											lowerCAmelCase      :list				  = []
											lowerCAmelCase      :dict				  = {}
					def 					UpperCAmelCase__   (       self       :  Optional[int]      )  ->					Union[str, Any]:
											return self._keys
					def 					UpperCAmelCase__   (       self       :  Dict      )  ->					Optional[Any]:
											return sum(1 for slot in self.values if slot is not None      ) / (
											    self.size_table * self.charge_factor
											)
					def 					UpperCAmelCase__   (       self       :  Any    ,   UpperCAmelCase       :  List[str]      )  ->					int:
											return key % self.size_table
					def 					UpperCAmelCase__   (       self       :  Dict    ,   UpperCAmelCase       :  Union[str, Any]      )  ->					int:
											print(f"""step {step_ord}"""      )
											print(list(range(len(self.values      )      )      )      )
											print(self.values      )
					def 					UpperCAmelCase__   (       self       :  Any    ,   UpperCAmelCase       :  Dict      )  ->					Any:
											lowerCAmelCase      :List[str]				  = 1
											lowerCAmelCase      :Union[str, Any]				  = values
											for value in values:
																	self.insert_data(UpperCAmelCase      )
																	self._step_by_step(UpperCAmelCase      )
																	i += 1
					def 					UpperCAmelCase__   (       self       :  str    ,   UpperCAmelCase       :  Dict    ,   UpperCAmelCase       :  Union[str, Any]      )  ->					Optional[Any]:
											lowerCAmelCase      :List[Any]				  = data
											lowerCAmelCase      :str				  = data
					def 					UpperCAmelCase__   (       self       :  Optional[int]    ,   UpperCAmelCase       :  str    ,   UpperCAmelCase       :  str=None      )  ->					Tuple:
											lowerCAmelCase      :Optional[Any]				  = self.hash_function(key + 1      )

											while self.values[new_key] is not None and self.values[new_key] != key:
																	if self.values.count(UpperCAmelCase      ) > 0:
																							lowerCAmelCase      :Tuple				  = self.hash_function(new_key + 1      )
																	else:
																							lowerCAmelCase      :Union[str, Any]				  = None
																							break

											return new_key
					def 					UpperCAmelCase__   (       self       :  Any      )  ->					Any:
											lowerCAmelCase      :Optional[Any]				  = [value for value in self.values if value is not None]
											lowerCAmelCase      :List[str]				  = next_prime(self.size_table    ,   factor=2      )
											self._keys.clear()
											lowerCAmelCase      :int				  = [None] * self.size_table  # hell's pointers D: don't DRY ;/
											for value in survivor_values:
																	self.insert_data(UpperCAmelCase      )
					def 					UpperCAmelCase__   (       self       :  Optional[int]    ,   UpperCAmelCase       :  Tuple      )  ->					int:
											lowerCAmelCase      :Union[str, Any]				  = self.hash_function(UpperCAmelCase      )

											if self.values[key] is None:
																	self._set_value(UpperCAmelCase    ,   UpperCAmelCase      )

											elif self.values[key] == data:
																	pass

											else:
																	lowerCAmelCase      :Tuple				  = self._collision_resolution(UpperCAmelCase    ,   UpperCAmelCase      )
																	if collision_resolution is not None:
																							self._set_value(UpperCAmelCase    ,   UpperCAmelCase      )
																	else:
																							self.rehashing()
																							self.insert_data(UpperCAmelCase      )