




"""simple docstring"""




import math







def      __UpperCAmelCase     ( __UpperCamelCase	,				__UpperCamelCase = 0	,				__UpperCamelCase = 0	):
			__lowercase			:  List[Any]								=       end or len(__UpperCamelCase	)
			for i in range(__UpperCamelCase	,				__UpperCamelCase	):
						__lowercase			:  Any								=       i
						__lowercase			:  str								=       array[i]
						while temp_index != start and temp_index_value < array[temp_index - 1]:
									__lowercase			:  Union[str, Any]								=       array[temp_index - 1]
									temp_index -= 1
						__lowercase			:  List[str]								=       temp_index_value
			return array







def      __UpperCAmelCase     ( __UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	):  # Max Heap
			__lowercase			:  Dict								=       index
			__lowercase			:  Optional[Any]								=       2 * index + 1  # Left Node
			__lowercase			:  str								=       2 * index + 2  # Right Node

			if left_index < heap_size and array[largest] < array[left_index]:
						__lowercase			:  str								=       left_index

			if right_index < heap_size and array[largest] < array[right_index]:
						__lowercase			:  int								=       right_index

			if largest != index:
						__lowercase			,__lowercase			:  Union[str, Any]								=       array[largest], array[index]
						heapify(__UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	)







def      __UpperCAmelCase     ( __UpperCamelCase	):
			__lowercase			:  List[str]								=       len(__UpperCamelCase	)

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

			for i in range(n - 1	,				0	,				-1	):
						__lowercase			,__lowercase			:  Optional[int]								=       array[0], array[i]
						heapify(__UpperCamelCase	,				0	,				__UpperCamelCase	)

			return array







def      __UpperCAmelCase     ( __UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	):
			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      __UpperCAmelCase     ( __UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	,				__UpperCamelCase	):
			__lowercase			:  int								=       low
			__lowercase			:  Dict								=       high
			while True:
						while array[i] < pivot:
									i += 1
						j -= 1
						while pivot < array[j]:
									j -= 1
						if i >= j:
									return i
						__lowercase			,__lowercase			:  str								=       array[j], array[i]
						i += 1







def      __UpperCAmelCase     ( __UpperCamelCase	):
			if len(__UpperCamelCase	) == 0:
						return array
			__lowercase			:  Tuple								=       2 * math.ceil(math.loga(len(__UpperCamelCase	)	)	)
			__lowercase			:  Dict								=       16
			return intro_sort(__UpperCamelCase	,				0	,				len(__UpperCamelCase	)	,				__UpperCamelCase	,				__UpperCamelCase	)







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


if __name__ == "__main__":
			import doctest

			doctest.testmod()

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










# Author: OMKAR PATHAK, Nwachukwu Chidiebere

# Use a Python dictionary to construct the graph.
from __future__ import annotations

from pprint import pformat
from typing import Generic, TypeVar

a__      :     Optional[int]         =		TypeVar('T')





class UpperCAmelCase_				( Generic[T] ):


  def __init__(							self ,__snake_case = True ):



       """simple docstring"""





       A_          =       {}  # dictionary of lists
       A_          =       directed


  def 						__UpperCAmelCase     (							self ,__snake_case ,__snake_case ):



       """simple docstring"""





       if not self.directed:  # For undirected graphs
            # if both source vertex and destination vertex are both present in the
            # adjacency list, add destination vertex to source vertex list of adjacent
            # vertices and add source vertex to destination vertex list of adjacent
            # vertices.
            if source_vertex in self.adj_list and destination_vertex in self.adj_list:
                 self.adj_list[source_vertex].append(__snake_case )
                 self.adj_list[destination_vertex].append(__snake_case )
            # if only source vertex is present in adjacency list, add destination vertex
            # to source vertex list of adjacent vertices, then create a new vertex with
            # destination vertex as key and assign a list containing the source vertex
            # as it's first adjacent vertex.
            elif source_vertex in self.adj_list:
                 self.adj_list[source_vertex].append(__snake_case )
                 A_          =       [source_vertex]
            # if only destination vertex is present in adjacency list, add source vertex
            # to destination vertex list of adjacent vertices, then create a new vertex
            # with source vertex as key and assign a list containing the source vertex
            # as it's first adjacent vertex.
            elif destination_vertex in self.adj_list:
                 self.adj_list[destination_vertex].append(__snake_case )
                 A_          =       [destination_vertex]
            # if both source vertex and destination vertex are not present in adjacency
            # list, create a new vertex with source vertex as key and assign a list
            # containing the destination vertex as it's first adjacent vertex also
            # create a new vertex with destination vertex as key and assign a list
            # containing the source vertex as it's first adjacent vertex.
            else:
                 A_          =       [destination_vertex]
                 A_          =       [source_vertex]
       else:  # For directed graphs
            # if both source vertex and destination vertex are present in adjacency
            # list, add destination vertex to source vertex list of adjacent vertices.
            if source_vertex in self.adj_list and destination_vertex in self.adj_list:
                 self.adj_list[source_vertex].append(__snake_case )
            # if only source vertex is present in adjacency list, add destination
            # vertex to source vertex list of adjacent vertices and create a new vertex
            # with destination vertex as key, which has no adjacent vertex
            elif source_vertex in self.adj_list:
                 self.adj_list[source_vertex].append(__snake_case )
                 A_          =       []
            # if only destination vertex is present in adjacency list, create a new
            # vertex with source vertex as key and assign a list containing destination
            # vertex as first adjacent vertex
            elif destination_vertex in self.adj_list:
                 A_          =       [destination_vertex]
            # if both source vertex and destination vertex are not present in adjacency
            # list, create a new vertex with source vertex as key and a list containing
            # destination vertex as it's first adjacent vertex. Then create a new vertex
            # with destination vertex as key, which has no adjacent vertex
            else:
                 A_          =       [destination_vertex]
                 A_          =       []

       return self




  def __repr__(							self ):



       """simple docstring"""





       return pformat(self.adj_list )



