
"""simple docstring"""




from __future__ import annotations

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

def     UpperCamelCase_    (						SCREAMING_SNAKE_CASE_,	SCREAMING_SNAKE_CASE_     ):
					SCREAMING_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_    (						SCREAMING_SNAKE_CASE_     ):
					SCREAMING_SNAKE_CASE           =      len(_UpperCAmelCase     )
					if length <= 1:
										return list_ad
					SCREAMING_SNAKE_CASE           =      length // 2
					return merge(sortlist_ad(list_ad[:middle]     ),	sortlist_ad(list_ad[middle:]     )     )

def     UpperCamelCase_    (						SCREAMING_SNAKE_CASE_     ):




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

					return result


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







'''simple docstring'''


from __future__ import annotations




def       A							(      _UpperCAmelCase   :				list					)  ->				int | float:


  '''simple docstring'''




  __lowerCAmelCase		:    List[Any]			     =  sorted(_UpperCAmelCase					)
  __lowerCAmelCase		:    List[str]			     =  len(_UpperCAmelCase					)
  __lowerCAmelCase		:    Any			     =  length >> 1
  return (
      (sorted_list[mid_index] + sorted_list[mid_index - 1]) / 2
      if length % 2 == 0
      else sorted_list[mid_index]
  )




def       A							(      )  ->				Union[str, Any]:


  '''simple docstring'''




  import doctest

  doctest.testmod()


if __name__ == "__main__":
    main()





