




"""simple docstring"""




def lowercase_  (       _snake_case						):
							if len(_snake_case						) > 1:
														SCREAMING_SNAKE_CASE__						:	Optional[int]									=       len(_snake_case						) // 2  # Finds the middle of the array
														SCREAMING_SNAKE_CASE__						:	int									=       arr[
														    :middle_length
														]  # Creates an array of the elements in the first half.
														SCREAMING_SNAKE_CASE__						:	int									=       arr[
														    middle_length:
														]  # Creates an array of the elements in the second half.
														SCREAMING_SNAKE_CASE__						:	Union[str, Any]									=       len(_snake_case						)
														SCREAMING_SNAKE_CASE__						:	int									=       len(_snake_case						)
														merge(_snake_case						)  # Starts sorting the left.
														merge(_snake_case						)  # Starts sorting the right
														SCREAMING_SNAKE_CASE__						:	Any									=       0  # Left Counter
														SCREAMING_SNAKE_CASE__						:	Optional[int]									=       0  # Right Counter
														SCREAMING_SNAKE_CASE__						:	int									=       0  # Position Counter
														while (
														    left_index < left_size and right_index < right_size
														):  # Runs until the lowers size of the left and right are sorted.
																					if left_array[left_index] < right_array[right_index]:
																												SCREAMING_SNAKE_CASE__						:	Dict									=       left_array[left_index]
																												left_index += 1
																					else:
																												SCREAMING_SNAKE_CASE__						:	List[str]									=       right_array[right_index]
																												right_index += 1
																					index += 1
														while (
														    left_index < left_size
														):  # Adds the left over elements in the left half of the array
																					SCREAMING_SNAKE_CASE__						:	Optional[Any]									=       left_array[left_index]
																					left_index += 1
																					index += 1
														while (
														    right_index < right_size
														):  # Adds the left over elements in the right half of the array
																					SCREAMING_SNAKE_CASE__						:	Dict									=       right_array[right_index]
																					right_index += 1
																					index += 1
							return arr


if __name__ == "__main__":
					import doctest

					doctest.testmod()






"""simple docstring"""




def lowercase_  (       _snake_case       ,_snake_case       ,_snake_case						):
							SCREAMING_SNAKE_CASE__						:	Any									=       index
							SCREAMING_SNAKE_CASE__						:	List[Any]									=       2 * index + 1
							SCREAMING_SNAKE_CASE__						:	Any									=       2 * index + 2
							if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
														SCREAMING_SNAKE_CASE__						:	str									=       left_index

							if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
														SCREAMING_SNAKE_CASE__						:	Any									=       right_index

							if largest != index:
														SCREAMING_SNAKE_CASE__				,				SCREAMING_SNAKE_CASE__						:	Tuple									=       unsorted[index], unsorted[largest]
														heapify(_snake_case       ,_snake_case       ,_snake_case						)

def lowercase_  (       _snake_case						):
							SCREAMING_SNAKE_CASE__						:	List[Any]									=       len(_snake_case						)
							for i in range(n // 2 - 1       ,-1       ,-1						):
														heapify(_snake_case       ,_snake_case       ,_snake_case						)
							for i in range(n - 1       ,0       ,-1						):
														SCREAMING_SNAKE_CASE__				,				SCREAMING_SNAKE_CASE__						:	Any									=       unsorted[i], unsorted[0]
														heapify(_snake_case       ,0       ,_snake_case						)
							return unsorted


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




