


'''simple docstring'''



from __future__ import annotations



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



def       UpperCAmelCase__ (     UpperCAmelCase_   :    Optional[int]				,   UpperCAmelCase_   :    List[str]							)					->		Optional[int]:
     __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__ (     UpperCAmelCase_   :    Optional[Any]							)					->		Dict:
     __lowerCamelCase       :     Tuple        =		len(UpperCAmelCase_							)
     if length <= 1:
          return list_ad
     __lowerCamelCase       :     List[Any]        =		length // 2
     return merge(sortlist_ad(list_ad[:middle]							)				,   sortlist_ad(list_ad[middle:]							)							)



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

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

     return result


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










'''simple docstring'''



from typing import Literal

A__		: Tuple												=  """ABCDEFGHIJKLMNOPQRSTUVWXYZ"""



def       UpperCAmelCase__ (     UpperCAmelCase_   :    str				,   UpperCAmelCase_   :    str				,   UpperCAmelCase_   :    Literal["encrypt", "decrypt"]							)					->		str:
     __lowerCamelCase       :     Dict        =		LETTERS if mode == 'decrypt' else key
     __lowerCamelCase       :     Tuple        =		key if mode == 'decrypt' else LETTERS
     __lowerCamelCase       :     Optional[int]        =		''
     # loop through each symbol in the message
     for symbol in message:
          if symbol.upper() in chars_a:
               # encrypt/decrypt the symbol
               __lowerCamelCase       :     Optional[int]        =		chars_a.find(symbol.upper()							)
               if symbol.isupper():
                    translated += chars_b[sym_index].upper()
               else:
                    translated += chars_b[sym_index].lower()
          else:
               # symbol is not in LETTERS, just add it
               translated += symbol
     return translated



def       UpperCAmelCase__ (     UpperCAmelCase_   :    str				,   UpperCAmelCase_   :    str							)					->		str:
     return translate_message(UpperCAmelCase_				,   UpperCAmelCase_				,   'encrypt'							)



def       UpperCAmelCase__ (     UpperCAmelCase_   :    str				,   UpperCAmelCase_   :    str							)					->		str:
     return translate_message(UpperCAmelCase_				,   UpperCAmelCase_				,   'decrypt'							)



def       UpperCAmelCase__ (     )					->		None:
     __lowerCamelCase       :     Dict        =		'Hello World'
     __lowerCamelCase       :     str        =		'QWERTYUIOPASDFGHJKLZXCVBNM'
     __lowerCamelCase       :     Any        =		'decrypt'  # set to 'encrypt' or 'decrypt'

     if mode == "encrypt":
          __lowerCamelCase       :     Optional[int]        =		encrypt_message(UpperCAmelCase_				,   UpperCAmelCase_							)
     elif mode == "decrypt":
          __lowerCamelCase       :     List[str]        =		decrypt_message(UpperCAmelCase_				,   UpperCAmelCase_							)
     print(F'Using the key {key}, the {mode}ed message is: {translated}'							)


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      main()






