



'''simple docstring'''







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

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

		if largest != index:
				SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:Any										=      unsorted[index], unsorted[largest]
				heapify(SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     )







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE     ):
		SCREAMING_SNAKE_CASE_						:Optional[int]										=      len(SCREAMING_SNAKE_CASE     )
		for i in range(n // 2 - 1 ,		-1 ,		-1     ):
				heapify(SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     )
		for i in range(n - 1 ,		0 ,		-1     ):
				SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:int										=      unsorted[i], unsorted[0]
				heapify(SCREAMING_SNAKE_CASE ,		0 ,		SCREAMING_SNAKE_CASE     )
		return unsorted


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

from __future__ import annotations







def     A__	(       __A ,			__A						):







    '''simple docstring'''
    _lowerCamelCase  :		List[str]			    =    [None] * (len(__A						) + len(__A						))

    _lowerCamelCase  :		Optional[int]			    =    0  # pointer to current index for left Half
    _lowerCamelCase  :		List[str]			    =    0  # pointer to current index for the right Half
    _lowerCamelCase  :		List[str]			    =    0  # pointer to current index for the sorted array Half

    while pointera < len(__A						) and pointera < len(__A						):
        if left_half[pointera] < right_half[pointera]:
            _lowerCamelCase  :		Optional[Any]			    =    left_half[pointera]
            pointera += 1
            index += 1
        else:
            _lowerCamelCase  :		List[Any]			    =    right_half[pointera]
            pointera += 1
            index += 1
    while pointera < len(__A						):
        _lowerCamelCase  :		int			    =    left_half[pointera]
        pointera += 1
        index += 1

    while pointera < len(__A						):
        _lowerCamelCase  :		Optional[Any]			    =    right_half[pointera]
        pointera += 1
        index += 1

    return sorted_array







def     A__	(       __A						):







    '''simple docstring'''
    if len(__A						) <= 1:
        return array
    # the actual formula to calculate the middle element = left + (right - left) // 2
    # this avoids integer overflow in case of large N
    _lowerCamelCase  :		int			    =    0 + (len(__A						) - 0) // 2

    # Split the array into halves till the array length becomes equal to One
    # merge the arrays of single length returned by mergeSort function and
    # pass them into the merge arrays function which merges the array
    _lowerCamelCase  :		List[str]			    =    array[:middle]
    _lowerCamelCase  :		Optional[int]			    =    array[middle:]

    return merge(merge_sort(__A						) ,			merge_sort(__A						)						)


if __name__ == "__main__":
    import doctest

    doctest.testmod()




