






import math


def 				__lowerCamelCase     (							__lowerCAmelCase							:					list					,							__lowerCAmelCase							:					int = 0					,							__lowerCAmelCase							:					int = 0							)     ->  list:
   __UpperCamelCase	:			List[Any]					=					end or len(__lowerCAmelCase							)
   for i in range(__lowerCAmelCase					,							__lowerCAmelCase							):
      __UpperCamelCase	:			Union[str, Any]					=					i
      __UpperCamelCase	:			str					=					array[i]
      while temp_index != start and temp_index_value < array[temp_index - 1]:
         __UpperCamelCase	:			Dict					=					array[temp_index - 1]
         temp_index -= 1
      __UpperCamelCase	:			Tuple					=					temp_index_value
   return array


def 				__lowerCamelCase     (							__lowerCAmelCase							:					list					,							__lowerCAmelCase							:					int					,							__lowerCAmelCase							:					int							)     ->  None:  # Max Heap
   __UpperCamelCase	:			List[str]					=					index
   __UpperCamelCase	:			Tuple					=					2 * index + 1  # Left Node
   __UpperCamelCase	:			Optional[int]					=					2 * index + 2  # Right Node

   if left_index < heap_size and array[largest] < array[left_index]:
      __UpperCamelCase	:			Optional[Any]					=					left_index

   if right_index < heap_size and array[largest] < array[right_index]:
      __UpperCamelCase	:			Tuple					=					right_index

   if largest != index:
      __UpperCamelCase	,     __UpperCamelCase	:			List[Any]					=					array[largest], array[index]
      heapify(__lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase							)


def 				__lowerCamelCase     (							__lowerCAmelCase							:					list							)     ->  list:
   __UpperCamelCase	:			List[Any]					=					len(__lowerCAmelCase							)

   for i in range(n // 2					,							-1					,							-1							):
      heapify(__lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase							)

   for i in range(n - 1					,							0					,							-1							):
      __UpperCamelCase	,     __UpperCamelCase	:			Union[str, Any]					=					array[0], array[i]
      heapify(__lowerCAmelCase					,							0					,							__lowerCAmelCase							)

   return array


def 				__lowerCamelCase     (							__lowerCAmelCase							:					list					,							__lowerCAmelCase							:					int					,							__lowerCAmelCase							:					int					,							__lowerCAmelCase							:					int							)     ->  int:
   if (array[first_index] > array[middle_index]) != (
       array[first_index] > array[last_index]
   ):
      return array[first_index]
   elif (array[middle_index] > array[first_index]) != (
       array[middle_index] > array[last_index]
   ):
      return array[middle_index]
   else:
      return array[last_index]


def 				__lowerCamelCase     (							__lowerCAmelCase							:					list					,							__lowerCAmelCase							:					int					,							__lowerCAmelCase							:					int					,							__lowerCAmelCase							:					int							)     ->  int:
   __UpperCamelCase	:			Dict					=					low
   __UpperCamelCase	:			Any					=					high
   while True:
      while array[i] < pivot:
         i += 1
      j -= 1
      while pivot < array[j]:
         j -= 1
      if i >= j:
         return i
      __UpperCamelCase	,     __UpperCamelCase	:			int					=					array[j], array[i]
      i += 1


def 				__lowerCamelCase     (							__lowerCAmelCase							:					list							)     ->  list:
   if len(__lowerCAmelCase							) == 0:
      return array
   __UpperCamelCase	:			Optional[Any]					=					2 * math.ceil(math.loga(len(__lowerCAmelCase							)							)							)
   __UpperCamelCase	:			int					=					16
   return intro_sort(__lowerCAmelCase					,							0					,							len(__lowerCAmelCase							)					,							__lowerCAmelCase					,							__lowerCAmelCase							)


def 				__lowerCamelCase     (							__lowerCAmelCase							:					list					,							__lowerCAmelCase							:					int					,							__lowerCAmelCase							:					int					,							__lowerCAmelCase							:					int					,							__lowerCAmelCase							:					int							)     ->  list:
   while end - start > size_threshold:
      if max_depth == 0:
         return heap_sort(__lowerCAmelCase							)
      max_depth -= 1
      __UpperCamelCase	:			List[str]					=					median_of_a(__lowerCAmelCase					,							__lowerCAmelCase					,							start + ((end - start) // 2) + 1					,							end - 1							)
      __UpperCamelCase	:			Dict					=					partition(__lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase							)
      intro_sort(__lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase							)
      __UpperCamelCase	:			Optional[int]					=					p
   return insertion_sort(__lowerCAmelCase					,							__lowerCAmelCase					,							__lowerCAmelCase							)


if __name__ == "__main__":
       import doctest

       doctest.testmod()

       UpperCamelCase    							=      input('Enter numbers separated by a comma : ').strip()
       UpperCamelCase    							=      [float(item) for item in user_input.split(',')]
       print(sort(unsorted))











from __future__ import annotations


def 				__lowerCamelCase     (							__lowerCAmelCase							:					str					,							__lowerCAmelCase							:					Tuple					,							__lowerCAmelCase							:					int					,							__lowerCAmelCase							:					Tuple							)     ->  Optional[Any]:  # noqa: E741
   while r - l > 1:
      __UpperCamelCase	:			int					=					(l + r) // 2
      if v[m] >= key:
         __UpperCamelCase	:			Dict					=					m
      else:
         __UpperCamelCase	:			Optional[Any]					=					m  # noqa: E741
   return r


def 				__lowerCamelCase     (							__lowerCAmelCase							:					list[int]							)     ->  int:
   if len(__lowerCAmelCase							) == 0:
      return 0

   __UpperCamelCase	:			Optional[Any]					=					[0] * len(__lowerCAmelCase							)
   __UpperCamelCase	:			Optional[int]					=					1

   __UpperCamelCase	:			Union[str, Any]					=					v[0]

   for i in range(1					,							len(__lowerCAmelCase							)							):
      if v[i] < tail[0]:
         __UpperCamelCase	:			Dict					=					v[i]
      elif v[i] > tail[length - 1]:
         __UpperCamelCase	:			Optional[int]					=					v[i]
         length += 1
      else:
         __UpperCamelCase	:			List[Any]					=					v[i]

   return length


if __name__ == "__main__":
       import doctest

       doctest.testmod()



