


from __future__ import annotations






def    _UpperCAmelCase	(   __lowerCamelCase ,     __lowerCamelCase       )		->Any:


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






def    _UpperCAmelCase	(   __lowerCamelCase ,     __lowerCamelCase       )		->str:


 '''simple docstring'''
 snake_case   : Any	  =      []
 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	(   __lowerCamelCase       )		->Dict:


 '''simple docstring'''
 snake_case   : Any	  =      len(__lowerCamelCase       )
 if length <= 1:
  return list_ad
 snake_case   : Union[str, Any]	  =      length // 2
 return merge(sortlist_ad(list_ad[:middle]       ) ,     sortlist_ad(list_ad[middle:]       )       )






def    _UpperCAmelCase	(   __lowerCamelCase       )		->list[int]:


 '''simple docstring'''

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

 return result


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










from typing import Callable






def    _UpperCAmelCase	(   __lowerCamelCase       )		->Tuple:


 '''simple docstring'''

 def wrapper(__lowerCamelCase       ):
  snake_case   : str	  =      function_with_docstring.__doc__
  return target_function

 return wrapper






