




'''simple docstring'''



from __future__ import annotations







def      _UpperCamelCase	(_lowerCamelCase							:       List[Any]				,		_lowerCamelCase							:       str		)->				Optional[Any]:




     '''simple docstring'''





     __snake_case         =					0
     __snake_case         =					len(_lowerCamelCase		) - 1
     while left <= right:
          __snake_case         =					(left + right) // 2
          if left == right:
               if sorted_list[middle] < item:
                    __snake_case         =					middle + 1
               break
          elif sorted_list[middle] < item:
               __snake_case         =					middle + 1
          else:
               __snake_case         =					middle - 1
     sorted_list.insert(_lowerCamelCase				,		_lowerCamelCase		)
     return sorted_list







def      _UpperCamelCase	(_lowerCamelCase							:       Tuple				,		_lowerCamelCase							:       str		)->				Union[str, Any]:




     '''simple docstring'''





     __snake_case         =					[]
     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							:       str		)->				Optional[int]:




     '''simple docstring'''





     __snake_case         =					len(_lowerCamelCase		)
     if length <= 1:
          return list_ad
     __snake_case         =					length // 2
     return merge(sortlist_ad(list_ad[:middle]		)				,		sortlist_ad(list_ad[middle:]		)		)







def      _UpperCamelCase	(_lowerCamelCase							:       list[int]		)->				list[int]:




     '''simple docstring'''





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

     return result


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












'''simple docstring'''



def      _UpperCamelCase	(_lowerCamelCase							:       list				,		_lowerCamelCase							:       int		)->				int:




     '''simple docstring'''





     for index, item in enumerate(_lowerCamelCase		):
          if item == target:
               return index
     return -1







def      _UpperCamelCase	(_lowerCamelCase							:       list				,		_lowerCamelCase							:       int				,		_lowerCamelCase							:       int				,		_lowerCamelCase							:       int		)->				int:




     '''simple docstring'''





     if not (0 <= high < len(_lowerCamelCase		) and 0 <= low < len(_lowerCamelCase		)):
          raise Exception('''Invalid upper or lower bound!'''		)
     if high < low:
          return -1
     if sequence[low] == target:
          return low
     if sequence[high] == target:
          return high
     return rec_linear_search(_lowerCamelCase				,		low + 1				,		high - 1				,		_lowerCamelCase		)


if __name__ == "__main__":
     UpperCAmelCase_    :					List[Any]					      =						input('''Enter numbers separated by comma:\n''').strip()
     UpperCAmelCase_    :					Optional[int]					      =						[int(item.strip()) for item in user_input.split(''',''')]

     UpperCAmelCase_    :					List[str]					      =						int(input('''Enter a single number to be found in the list:\n''').strip())
     UpperCAmelCase_    :					Optional[int]					      =						linear_search(sequence, target)
     if result != -1:
          print(F"""linear_search({sequence}, {target}) = {result}""")
     else:
          print(F"""{target} was not found in {sequence}""")






